DP on Trees Diameter of Tree in DSA Java - Build from Scratch

DP on Trees: Diameter of Tree

📖 Scenario: Imagine you are working with a network of connected computers arranged like a tree. You want to find the longest path between any two computers in this network. This longest path is called the diameter of the tree.

🎯 Goal: Build a Java program that uses dynamic programming on trees to find the diameter of a given tree represented by edges.

📋 What You'll Learn

Create an adjacency list to represent the tree

Use a helper variable to track the maximum diameter found

Implement a depth-first search (DFS) function that returns the longest path from a node down to its descendants

Calculate the diameter by combining the two longest paths from children

Print the diameter of the tree

💡 Why This Matters

🌍 Real World

Finding the diameter of a tree is useful in network design, biology (evolution trees), and file system analysis to understand the longest communication or dependency path.

💼 Career

Understanding tree diameter and dynamic programming on trees is important for software engineers working on graph algorithms, network optimization, and competitive programming.

1

Create the tree adjacency list

Create an integer variable n with value 7 for number of nodes. Then create an adjacency list called tree as an ArrayList<ArrayList<Integer>> with n empty lists. Add edges to tree to represent these connections: 0-1, 0-2, 1-3, 1-4, 2-5, 2-6. Each edge should be added in both directions.

DSA Java

// Create variable n and adjacency list tree
// Add edges to tree
// Your code here

Hint

Use a loop to add n empty lists to tree. Then add each edge twice, once for each direction.

2

Add a variable to track the maximum diameter

Add a static integer variable called maxDiameter and initialize it to 0 to keep track of the longest diameter found so far.

DSA Java

import java.util.ArrayList;

public class TreeDiameter {
    static int n = 7;
    static ArrayList> tree = new ArrayList();
    // Add maxDiameter variable here
    // Your code here

    public static void main(String[] args) {
        for (int i = 0; i ());
        }
        tree.get(0).add(1);
        tree.get(1).add(0);
        tree.get(0).add(2);
        tree.get(2).add(0);
        tree.get(1).add(3);
        tree.get(3).add(1);
        tree.get(1).add(4);
        tree.get(4).add(1);
        tree.get(2).add(5);
        tree.get(5).add(2);
        tree.get(2).add(6);
        tree.get(6).add(2);
    }
}

Hint

Declare maxDiameter as a static integer variable and set it to zero.

3

Implement DFS to find longest paths and update diameter

Add a static method dfs that takes an integer node and an integer parent. It returns an integer representing the longest path from node down to its descendants. Inside dfs, find the two longest child paths, update maxDiameter with their sum if larger, and return the longest child path plus one.

DSA Java

import java.util.ArrayList;

public class TreeDiameter {
    static int n = 7;
    static ArrayList> tree = new ArrayList();
    static int maxDiameter = 0;

    public static int dfs(int node, int parent) {
        // Your code here
    }

    public static void main(String[] args) {
        for (int i = 0; i ());
        }
        tree.get(0).add(1);
        tree.get(1).add(0);
        tree.get(0).add(2);
        tree.get(2).add(0);
        tree.get(1).add(3);
        tree.get(3).add(1);
        tree.get(1).add(4);
        tree.get(4).add(1);
        tree.get(2).add(5);
        tree.get(5).add(2);
        tree.get(2).add(6);
        tree.get(6).add(2);
    }
}

Hint

Use two variables to track the longest and second longest child paths. Update maxDiameter with their sum. Return the longest path plus one.

4

Call DFS and print the diameter

In the main method, after building the tree, call dfs(0, -1) to start DFS from node 0 with no parent. Then print the value of maxDiameter using System.out.println(maxDiameter);.

DSA Java

import java.util.ArrayList;

public class TreeDiameter {
    static int n = 7;
    static ArrayList> tree = new ArrayList();
    static int maxDiameter = 0;

    public static int dfs(int node, int parent) {
        int max1 = 0;
        int max2 = 0;
        for (int child : tree.get(node)) {
            if (child == parent) continue;
            int length = dfs(child, node);
            if (length > max1) {
                max2 = max1;
                max1 = length;
            } else if (length > max2) {
                max2 = length;
            }
        }
        maxDiameter = Math.max(maxDiameter, max1 + max2);
        return max1 + 1;
    }

    public static void main(String[] args) {
        for (int i = 0; i ());
        }
        tree.get(0).add(1);
        tree.get(1).add(0);
        tree.get(0).add(2);
        tree.get(2).add(0);
        tree.get(1).add(3);
        tree.get(3).add(1);
        tree.get(1).add(4);
        tree.get(4).add(1);
        tree.get(2).add(5);
        tree.get(5).add(2);
        tree.get(2).add(6);
        tree.get(6).add(2);
        // Call dfs and print maxDiameter
        // Your code here
    }
}

Hint

Call dfs(0, -1) to start from node 0 with no parent. Then print maxDiameter.

Practice

1. What does the diameter of a tree represent in graph theory?

easy

A. The number of leaf nodes in the tree

B. The number of nodes in the tree

C. The height of the tree from the root

D. The longest path between any two nodes in the tree

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes in a tree, not just from the root.

2. Step 2: Differentiate from other tree properties

   Height is the longest path from root to leaf, number of nodes and leaves are counts, not paths.

3. Final Answer:

   The longest path between any two nodes in the tree -> Option D

4. Quick Check:

   Diameter = Longest path [OK]

Hint: Diameter = longest path between any two nodes [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of path length
• Assuming diameter is from root only

2. Which of the following Java code snippets correctly initializes an adjacency list for a tree with n nodes?

easy

A. ArrayList[] tree = new ArrayList[n];

B. List<Integer>[] tree = new ArrayList[n]; for(int i=0; i();

C. List<Integer> tree = new List[n];

D. ArrayList<Integer> tree = new ArrayList<>(n);

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of lists, each initialized to an empty ArrayList to hold neighbors.

2. Step 2: Check each option

   List<Integer>[] tree = new ArrayList[n]; for(int i=0; i(); correctly creates an array of lists and initializes each element. Others either lack initialization or use wrong types.

3. Final Answer:

   List<Integer>[] tree = new ArrayList[n]; for(int i=0; i -> Option B

4. Quick Check:

   Array of lists with initialization [OK]

Hint: Initialize each list in array separately [OK]

Common Mistakes:

• Not initializing each list element
• Using raw List without generics
• Wrong array type declaration

3. Consider the following Java method to find the diameter of a tree. What will be the output if the tree edges are: 0-1, 1-2, 1-3?

int diameter = 0;
int dfs(int node, int parent, List<Integer>[] tree) {
  int max1 = 0, max2 = 0;
  for (int child : tree[node]) {
    if (child == parent) continue;
    int height = dfs(child, node, tree) + 1;
    if (height > max1) {
      max2 = max1;
      max1 = height;
    } else if (height > max2) {
      max2 = height;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1;
}
// call dfs(0, -1, tree) and then print diameter;

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Build the tree and understand paths

   The tree edges are 0-1, 1-2, 1-3. The longest path is from node 2 to node 0 or 3 to 0, length 2 edges.

2. Step 2: Trace DFS and diameter calculation

   DFS calculates max heights from children and updates diameter as sum of two largest heights. Here, diameter becomes 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest path length = 2 edges [OK]

Hint: Diameter = sum of two largest subtree heights [OK]

Common Mistakes:

• Counting nodes instead of edges
• Ignoring parent check in DFS
• Miscomputing max heights

4. The following code attempts to compute the diameter of a tree but has a bug. What is the bug?

int diameter = 0;
int dfs(int node, int parent, List<Integer>[] tree) {
  int max1 = 0, max2 = 0;
  for (int child : tree[node]) {
    int height = dfs(child, node, tree) + 1;
    if (height > max1) {
      max2 = max1;
      max1 = height;
    } else if (height > max2) {
      max2 = height;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1;
}
// call dfs(0, -1, tree);

medium

A. Missing check to skip parent node in DFS

B. Incorrect update of diameter variable

C. Wrong return value from DFS

D. Initialization of max1 and max2 is incorrect

Solution

1. Step 1: Analyze DFS loop over children

   The code calls dfs on all children but does not skip the parent node, causing infinite recursion or stack overflow.

2. Step 2: Identify missing condition

   There should be a condition to continue if child == parent to avoid revisiting the parent.

3. Final Answer:

   Missing check to skip parent node in DFS -> Option A

4. Quick Check:

   Skip parent to prevent infinite recursion [OK]

Hint: Always skip parent node in tree DFS [OK]

Common Mistakes:

• Forgetting to skip parent node
• Misplacing diameter update
• Returning wrong height

5. You want to find the diameter of a weighted tree where edges have positive weights. Which modification to the standard diameter DFS approach is correct?

hard

A. Use BFS twice without considering weights

B. Ignore weights and count edges as 1 each

C. Add edge weights to the height calculation instead of just adding 1

D. Calculate diameter by summing all edge weights in the tree

Solution

1. Step 1: Understand weighted tree diameter

   In weighted trees, path length is sum of edge weights, not just number of edges.

2. Step 2: Modify DFS height calculation

   Instead of adding 1 for each edge, add the actual edge weight to the height returned by DFS.

3. Step 3: Update diameter similarly

   Diameter is max sum of two largest weighted heights from children.

4. Final Answer:

   Add edge weights to the height calculation instead of just adding 1 -> Option C

5. Quick Check:

   Use weights in height sums for weighted diameter [OK]

Hint: Add edge weights, not just count edges [OK]

Common Mistakes:

• Ignoring weights in diameter calculation
• Using BFS without weights
• Summing all edges instead of longest path