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

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

DFS to children

↓

Compute max depths from children

↓

Update diameter using top two depths

↓

Return max depth to parent

↓

Repeat for all nodes

↓

Final diameter is max found

We start DFS from any node, compute max depths from children, update diameter using top two depths, and return max depth to parent until all nodes are processed.

Execution Sample

DSA C

int dfs(int node, int parent) {
  int max1 = 0, max2 = 0;
  for (each child of node) {
    if (child != parent) {
      int depth = dfs(child, node);
      if (depth > max1) { max2 = max1; max1 = depth; } else if (depth > max2) max2 = depth;
    }
  }
  diameter = max(diameter, max1 + max2);
  return max1 + 1;
}

This code runs DFS to find max depths from children, updates diameter with sum of top two depths, and returns max depth to parent.

Execution Table

Step	Operation	Node Visited	Max Depths from Children	Diameter Update	Return Depth	Visual State
1	Start DFS	Node 1	max1=0, max2=0	diameter=0	Returns after children	1
2	DFS child Node 2	Node 2	max1=0, max2=0	diameter=0	Returns 1	1 -> 2
3	Update Node 1 depths	Node 1	max1=1, max2=0	diameter=1	Returns 2	1 -> 2
4	DFS child Node 3	Node 3	max1=0, max2=0	diameter=1	Returns 1	1 -> 2, 1 -> 3
5	Update Node 1 depths	Node 1	max1=1, max2=1	diameter=2	Returns 2	1 -> 2, 1 -> 3
6	DFS child Node 4	Node 4	max1=0, max2=0	diameter=2	Returns 1	1 -> 2, 1 -> 3, 3 -> 4
7	Update Node 3 depths	Node 3	max1=1, max2=0	diameter=2	Returns 2	1 -> 2, 1 -> 3, 3 -> 4
8	Update Node 1 depths	Node 1	max1=2, max2=1	diameter=3	Returns 3	1 -> 2, 1 -> 3, 3 -> 4
9	DFS child Node 5	Node 5	max1=0, max2=0	diameter=3	Returns 1	3 -> 5
10	Update Node 3 depths	Node 3	max1=1, max2=1	diameter=3	Returns 2	3 -> 4, 3 -> 5
11	Update Node 1 depths	Node 1	max1=2, max2=2	diameter=4	Returns 3	1 -> 2, 1 -> 3, 3 -> 4, 3 -> 5
12	End DFS	Node 1	max1=2, max2=2	diameter=4	Final diameter=4	Full tree

💡 All nodes visited, diameter updated with max sum of two depths, DFS ends.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	Final
diameter	0	0	2	3	4	4
max1 (Node 1)	0	1	1	2	2	2
max2 (Node 1)	0	0	1	1	2	2
Return Depth (Node 1)	N/A	2	2	3	3	3

Key Moments - 3 Insights

Why do we keep track of two maximum depths (max1 and max2) at each node?

Because the diameter can pass through the current node combining two longest paths from different children. See execution_table steps 5 and 11 where diameter updates use max1 + max2.

Why do we return max1 + 1 from the DFS function?

We return max1 + 1 to represent the longest path from current node down to a leaf including the current node itself. This is shown in execution_table steps 3, 5, 8, and 11.

Why do we ignore the parent node in DFS traversal?

To avoid revisiting the node we came from and prevent infinite loops. This is implied in the code and shown in execution_table where children are visited excluding parent.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the diameter value after updating Node 1?

A 2

B 1

C 3

D 0

💡 Hint

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

At which step does the diameter first become 4?

A Step 8

B Step 6

C Step 11

D Step 12

💡 Hint

Look at the 'Diameter Update' column in execution_table rows for diameter=4.

If we did not track max2 (second max depth), what would be the diameter after step 11?

A 4

B 3

C 2

D 1

💡 Hint

Without max2, diameter updates use only max1, see how diameter changes in execution_table.

Concept Snapshot

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

Full Transcript

We find the diameter of a tree using dynamic programming with DFS. Starting from any node, we explore children and compute the maximum depths from them. At each node, we keep track of the two largest depths (max1 and max2). The diameter is updated by the sum of these two depths, representing the longest path passing through that node. We return max1 + 1 to the parent to represent the longest path including the current node. This process repeats until all nodes are visited, and the maximum diameter found is the tree's diameter.