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

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

Run DFS to find farthest node A

↓

Run DFS from node A to find farthest node B

↓

Diameter is distance between A and B

↓

Use DP to store max depths during DFS

↓

Update diameter with max sum of two depths at each node

↓

Return final diameter

Find diameter by two DFS traversals and use DP to store max depths for efficient calculation.

Execution Sample

DSA Typescript

function diameterOfTree(adj: number[][]): number {
  let diameter = 0;
  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of adj[node]) {
      if (child === parent) continue;
      const depth = dfs(child, node) + 1;
      if (depth > max1) {
        max2 = max1;
        max1 = depth;
      } else if (depth > max2) {
        max2 = depth;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return max1;
  }
  dfs(0, -1);
  return diameter;
}

Calculate tree diameter by DFS and DP storing max depths at each node.

Execution Table

Step	Operation	Node Visited	Max Depths (max1, max2)	Diameter Update	Visual State
1	Start DFS from node 0	0	(0,0)	diameter=0	0
2	Visit child 1 of node 0	1	(0,0)	diameter=0	0 -> 1
3	Visit child 3 of node 1	3	(0,0)	diameter=0	0 -> 1 -> 3
4	Return depth 1 from node 3	3	(0,0)	diameter=0	0 -> 1 -> 3
5	Update max depths at node 1: max1=1, max2=0	1	(1,0)	diameter=0	0 -> 1
6	Visit child 2 of node 0	2	(0,0)	diameter=0	0 -> 2
7	Visit child 4 of node 2	4	(0,0)	diameter=0	0 -> 2 -> 4
8	Return depth 1 from node 4	4	(0,0)	diameter=0	0 -> 2 -> 4
9	Update max depths at node 2: max1=1, max2=0	2	(1,0)	diameter=0	0 -> 2
10	Update max depths at node 0: max1=1 (from 1), max2=1 (from 2)	0	(1,1)	diameter=2	0
11	Diameter updated to max1+max2=2	0	(1,1)	diameter=2	Tree diameter path length = 2
12	DFS complete, return diameter	-	-	diameter=2	Final diameter = 2

💡 DFS completes after visiting all nodes; diameter is max sum of two max depths at any node.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 9	After Step 10	Final
diameter	0	0	0	0	2	2
max1 (node 0)	0	0	0	0	1	1
max2 (node 0)	0	0	0	0	1	1
max1 (node 1)	0	1	1	1	1	1
max2 (node 1)	0	0	0	0	0	0
max1 (node 2)	0	0	0	1	1	1
max2 (node 2)	0	0	0	0	0	0

Key Moments - 3 Insights

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

Because the diameter can pass through the current node combining two longest paths from its children. See execution_table step 10 where diameter updates using max1 + max2.

Why do we ignore the parent node during DFS?

To avoid revisiting the node we came from and prevent infinite loops. This is shown in the code snippet where child === parent is skipped.

How does the diameter relate to the max depths stored at nodes?

Diameter is the longest path between any two nodes, which equals the sum of two largest depths from a node. Execution_table step 11 shows diameter updated as max1 + max2.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what are the max depths (max1, max2) at node 0?

A (0,0)

B (2,0)

C (1,1)

D (1,0)

💡 Hint

Check the 'Max Depths (max1, max2)' column at step 10 in execution_table.

At which step does the diameter first update to a non-zero value?

A Step 5

B Step 10

C Step 9

D Step 12

💡 Hint

Look at the 'Diameter Update' column in execution_table to find when diameter changes from 0.

If the tree had only one node, what would be the diameter according to variable_tracker?

A 0

B 1

C Undefined

D 2

💡 Hint

Diameter starts at 0 and only updates when there are edges; see 'diameter' variable in variable_tracker.

Concept Snapshot

DP on Trees Diameter:
- Use DFS twice or DP during DFS
- Track two max depths (max1, max2) at each node
- Diameter = max sum of max1 + max2 over all nodes
- Ignore parent in DFS to avoid cycles
- Return final diameter after DFS completes

Full Transcript

To find the diameter of a tree, we run a depth-first search (DFS) starting from any node to find the farthest node A. Then, we run DFS again from node A to find the farthest node B. The distance between A and B is the diameter. During DFS, we use dynamic programming to store the two largest depths (max1 and max2) from each node's children. The diameter is updated as the maximum sum of these two depths at any node. We skip the parent node during DFS to avoid revisiting nodes. The final diameter is returned after all nodes are visited.