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

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

DFS to find farthest node A

↓

DFS from node A to find farthest node B

↓

Diameter = distance between A and B

↓

Use DP to store max depths at each node

↓

Calculate max path through each node

↓

Update global diameter if path is longer

↓

Return final diameter

We start DFS from any node to find the farthest node A, then DFS from A to find farthest node B. The distance between A and B is the diameter. DP stores max depths to compute longest paths through nodes.

Execution Sample

DSA Javascript

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

This code uses DFS and DP to find the diameter of a tree represented by adjacency list.

Execution Table

Step	Operation	Node Visited	Max Depths (max1, max2)	Diameter Update	Visual State
1	Start DFS at node 0	0	(0,0)	0	0
2	Visit child 1 of node 0	1	(0,0)	0	0 -> 1
3	Visit child 3 of node 1	3	(0,0)	0	0 -> 1 -> 3
4	Return depth 1 from node 3	3	(0,0)	0	0 -> 1 -> 3
5	Update max depths at node 1	1	(1,0)	0	0 -> 1 -> 3
6	Return depth 2 from node 1	1	(1,0)	0	0 -> 1 -> 3
7	Visit child 2 of node 0	2	(0,0)	0	0 -> 2
8	Visit child 4 of node 2	4	(0,0)	0	0 -> 2 -> 4
9	Return depth 1 from node 4	4	(0,0)	0	0 -> 2 -> 4
10	Update max depths at node 2	2	(1,0)	0	0 -> 2 -> 4
11	Return depth 2 from node 2	2	(1,0)	0	0 -> 2 -> 4
12	Update max depths at node 0	0	(2,2)	4	0 -> 1 -> 3 and 0 -> 2 -> 4
13	Return depth 3 from node 0	0	(2,2)	4	0 -> 1 -> 3 and 0 -> 2 -> 4
14	DFS complete	-	-	4	Diameter = 4
15	Return diameter	-	-	4	Final diameter = 4

💡 DFS completes after visiting all nodes; diameter updated to max path length 4

Variable Tracker

Variable	Start	After Step 5	After Step 10	After Step 12	Final
diameter	0	0	0	4	4
max1 (node 0)	0	-	-	2	2
max2 (node 0)	0	-	-	2	2
max1 (node 1)	0	1	-	-	-
max2 (node 1)	0	0	-	-	-
max1 (node 2)	0	-	1	-	-
max2 (node 2)	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 node combining two longest child paths. max1 and max2 store the top two depths to calculate this combined path length (see steps 12 and 13).

Why do we update diameter with max1 + max2 instead of just max1?

max1 + max2 represents the longest path passing through the current node using two different branches. max1 alone is just one branch's depth. This is why diameter updates at step 12 with 2 + 2 = 4.

Why does DFS return max1 + 1 instead of max1?

We add 1 to include the current node's edge to its parent. This helps parent nodes calculate their max depths correctly (see return values at steps 6, 11, and 13).

Visual Quiz - 3 Questions

Look at the execution table at step 12. What are the max depths (max1, max2) at node 0?

A (1, 0)

B (2, 2)

C (0, 0)

D (3, 1)

💡 Hint

Check the 'Max Depths (max1, max2)' column at step 12 in the execution table.

At which step does the diameter get updated to 4?

A Step 12

B Step 5

C Step 10

D Step 14

💡 Hint

Look at the 'Diameter Update' column in the execution table to find when diameter changes to 4.

If node 3 had an additional child increasing its depth, how would diameter change at step 12?

A Diameter would decrease because max2 would become smaller

B Diameter would stay the same because node 0 max depths don't change

C Diameter would increase because max1 at node 1 would increase

D Diameter would reset to 0

💡 Hint

Consider how increasing depth at node 3 affects max depths at node 1 and then node 0 in variable_tracker.

Concept Snapshot

Diameter of Tree using DP and DFS:
- Use DFS to find max depths of children
- Track two largest depths (max1, max2) at each node
- Diameter = max of (max1 + max2) over all nodes
- Return max1 + 1 for parent's depth calculation
- Diameter is longest path between any two nodes in tree

Full Transcript

This visualization shows how to find the diameter of a tree using dynamic programming and depth-first search. We start DFS from node 0, visiting children recursively. At each node, we track the two largest depths from its children (max1 and max2). The diameter is updated as the maximum sum of these two depths, representing the longest path passing through that node. The DFS returns max1 + 1 to include the current node's edge for its parent. The execution table traces each step, showing node visits, depth updates, and diameter changes. Key moments clarify why two max depths are tracked and why diameter updates use their sum. The quiz tests understanding of these steps and their effects on diameter calculation.

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 definition of diameter

   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 is 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 JavaScript code snippets correctly initializes an adjacency list for a tree with 3 nodes?

easy

A. const tree = {0: [1, 2], 1: [0], 2: [0]};

B. const tree = [[1, 2], [], []];

C. const tree = {0: 1, 1: 2, 2: 0};

D. const tree = [0, 1, 2];

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list maps each node to an array of its connected nodes.

2. Step 2: Check each option

   const tree = {0: [1, 2], 1: [0], 2: [0]}; uses an object with arrays for neighbors, correct for adjacency list. const tree = [[1, 2], [], []]; misses reverse edges from 1 and 2 to 0. const tree = {0: 1, 1: 2, 2: 0}; maps nodes to single nodes, not arrays. const tree = [0, 1, 2]; is just a list of nodes, no edges.

3. Final Answer:

   const tree = {0: [1, 2], 1: [0], 2: [0]}; -> Option A

4. Quick Check:

   Adjacency list = Object with arrays [OK]

Hint: Adjacency list maps nodes to arrays of neighbors [OK]

Common Mistakes:

• Using single values instead of arrays for neighbors
• Confusing arrays of nodes with adjacency lists
• Not including reverse edges in undirected tree

3. Consider the following JavaScript code to find the diameter of a tree represented as an adjacency list. What will be the output?

const tree = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1, 4], 4: [3]};
let maxDiameter = 0;
function dfs(node, parent) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    if (child === parent) continue;
    const length = dfs(child, node) + 1;
    if (length > max1) {
      max2 = max1;
      max1 = length;
    } else if (length > max2) {
      max2 = length;
    }
  }
  maxDiameter = Math.max(maxDiameter, max1 + max2);
  return max1;
}
dfs(0, -1);
console.log(maxDiameter);

medium

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Trace DFS to find longest paths

   Starting at node 0, DFS explores children. The longest path is from node 2 to node 4 passing through 1 and 3, length 3 edges.

2. Step 2: Calculate diameter from max1 + max2

   At node 1, max1=2 (to node 4), max2=1 (to node 2), sum=3 edges. At node 3, max1=1 (to node 4), max2=0, sum=1. The maximum sum found is 3 edges.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Diameter = sum of two longest child paths at any node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring the second longest path in calculation
• Not skipping parent node in DFS

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

const tree = {0: [1], 1: [0, 2], 2: [1]};
let maxDiameter = 0;
function dfs(node) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    const length = dfs(child) + 1;
    if (length > max1) {
      max2 = max1;
      max1 = length;
    } else if (length > max2) {
      max2 = length;
    }
  }
  maxDiameter = Math.max(maxDiameter, max1 + max2);
  return max1;
}
dfs(0);
console.log(maxDiameter);

medium

A. Tree adjacency list is incorrectly defined

B. maxDiameter is not updated correctly

C. Missing parent check causes infinite recursion

D. DFS does not return correct path length

Solution

1. Step 1: Identify missing parent check in DFS

   The DFS function does not skip the parent node, causing it to revisit the previous node endlessly, leading to infinite recursion.

2. Step 2: Understand impact of missing parent check

   Without skipping the parent, the DFS calls loop back and forth between nodes, never terminating.

3. Final Answer:

   Missing parent check causes infinite recursion -> Option C

4. Quick Check:

   Always skip parent node in DFS to avoid loops [OK]

Hint: Always pass and skip parent node in DFS [OK]

Common Mistakes:

• Not passing parent node in DFS
• Assuming tree edges are directed
• Updating maxDiameter incorrectly

5. You have a tree with weighted edges represented as an adjacency list: {0: [[1, 3], [2, 5]], 1: [[0, 3], [3, 4]], 2: [[0, 5]], 3: [[1, 4]]}. How would you modify the diameter calculation to find the longest weighted path?

hard

A. Ignore weights and count edges only

B. Add edge weights to the DFS return values and update maxDiameter accordingly

C. Use BFS instead of DFS without weights

D. Sum all weights in the tree and divide by number of edges

Solution

1. Step 1: Incorporate edge weights in DFS

   Modify DFS to add the weight of each edge when calculating path lengths instead of just adding 1.

2. Step 2: Update maxDiameter with weighted sums

   At each node, update maxDiameter with the sum of the two longest weighted paths found among children.

3. Final Answer:

   Add edge weights to the DFS return values and update maxDiameter accordingly -> Option B

4. Quick Check:

   Weighted diameter needs weighted path sums [OK]

Hint: Add weights to path lengths in DFS for weighted diameter [OK]

Common Mistakes:

• Ignoring weights and counting edges only
• Using BFS without weights for diameter
• Summing all weights instead of longest path