DP on Trees Diameter of Tree in DSA Java - Execution Trace

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

DFS to children

↓

Compute max depths from children

↓

Update diameter with sum of top two depths

↓

Return max depth + 1 to parent

↓

Repeat for all nodes

↓

Final diameter is max found

We start DFS from any node, compute max depths of children, update diameter by sum of top two depths, and propagate max depth up to parent until all nodes are processed.

Execution Sample

DSA Java

int diameter = 0;
int dfs(Node node) {
  if (node == null) return 0;
  int max1 = 0, max2 = 0;
  for (Node child : node.children) {
    int depth = dfs(child);
    if (depth > max1) {
      max2 = max1;
      max1 = depth;
    } else if (depth > max2) {
      max2 = depth;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1 + 1;
}

This code runs DFS on tree nodes, tracks two largest depths from children, updates diameter, and returns max depth to parent.

Execution Table

Step	Operation	Node Visited	Max Depths from Children	Diameter Update	Return Depth	Visual State
1	Visit leaf node	Node 4	[]	diameter=0	1	4(null)
2	Visit leaf node	Node 5	[]	diameter=0	1	5(null)
3	Visit Node 2	Node 2	[1 (from 4), 1 (from 5)]	diameter=2	2	2 -> 4,5
4	Visit leaf node	Node 3	[]	diameter=2	1	3(null)
5	Visit root node	Node 1	[2 (from 2), 1 (from 3)]	diameter=3	3	1 -> 2,3
6	End	-	-	diameter=3	-	Final diameter = 3

💡 All nodes visited, diameter is max sum of two largest depths found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
diameter	0	0	0	2	2	3	3
max1	0	0	0	1	0	2	2
max2	0	0	0	1	0	1	1

Key Moments - 3 Insights

Why do we track two largest depths from children instead of just one?

Because the diameter can pass through the current node connecting two deepest subtrees. See execution_table step 3 and 5 where diameter updates use sum of top two depths.

Why do we return max1 + 1 instead of max1 + max2?

We return max1 + 1 as the max depth from current node to its parent, representing the longest path down one subtree. The sum max1 + max2 is used only to update diameter, not returned. See execution_table return depths.

What happens if the tree has only one node?

Diameter remains 0 because no edges exist. The DFS returns 1 for depth but diameter update never increases. This is implied by initial diameter=0 and no children in execution_table step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the diameter after visiting Node 2?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Diameter Update' column at step 3 in execution_table.

At which step does the diameter become 3?

A Step 5

B Step 2

C Step 3

D Step 6

💡 Hint

Look at the 'Diameter Update' column and find when diameter changes to 3.

If Node 3 had a child with depth 2, how would the diameter change at step 5?

A Diameter would stay 3

B Diameter would increase to 5

C Diameter would decrease

D Diameter would become 2

💡 Hint

Consider sum of top two depths from children at step 5 in execution_table.

Concept Snapshot

DP on Trees Diameter:
- Use DFS to find max depths from children
- Track top two max depths per node
- Update diameter = max(diameter, sum of top two depths)
- Return max depth + 1 to parent
- Diameter is longest path between any two nodes

Full Transcript

To find the diameter of a tree using dynamic programming, we perform a depth-first search starting from any node. At each node, we calculate the maximum depths from its children. We keep track of the two largest depths because the diameter may pass through the current node connecting these two deepest subtrees. We update the diameter by comparing the current diameter with the sum of these two depths. Then, we return the maximum depth plus one to the parent node. This process repeats until all nodes are visited. The final diameter is the maximum sum found. The code example shows this logic with variables max1 and max2 for the top depths and a global diameter variable updated during traversal.

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