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

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

Run DFS to find farthest node A

↓

Run DFS from 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

Find diameter by two DFS traversals and use DP to store max depths to compute longest path through nodes.

Execution Sample

DSA C++

int dfs(int node, int parent) {
  int max1 = 0, max2 = 0;
  for (auto child : graph[node]) {
    if (child == parent) continue;
    int depth = dfs(child, node) + 1;
    if (depth > max1) { max2 = max1; max1 = depth; }
    else if (depth > max2) max2 = depth;
  }
  diameter = max(diameter, max1 + max2);
  return max1;
}

DFS computes max depths of subtrees and updates diameter as sum of two largest depths at each node.

Execution Table

Step	Operation	Current Node	Max Depths (max1, max2)	Diameter Update	Visual State (Tree with depths)
1	Start DFS at node 1	1	(0,0)	diameter=0	1(0)
2	Visit child 2 of 1	2	(0,0)	diameter=0	1(0) -> 2(0)
3	Visit child 4 of 2	4	(0,0)	diameter=0	1(0) -> 2(0) -> 4(0)
4	No children for 4, return 0	4	(0,0)	diameter=0	4(0) leaf
5	Back to 2, max1=1 (from 4)	2	(1,0)	diameter=0	2(1) with child 4(0)
6	Visit child 5 of 2	5	(0,0)	diameter=0	2(1) -> 5(0)
7	No children for 5, return 0	5	(0,0)	diameter=0	5(0) leaf
8	Back to 2, max2=1 (from 5)	2	(1,1)	diameter=2	2(1) with children 4(0),5(0)
9	Update diameter = max(0,1+1)=2	2	(1,1)	diameter=2	Diameter updated at node 2
10	Return max1=1 to node 1	2	(1,1)	diameter=2	Return depth 1 from 2
11	Visit child 3 of 1	3	(0,0)	diameter=2	1(0) -> 3(0)
12	Visit child 6 of 3	6	(0,0)	diameter=2	3(0) -> 6(0)
13	No children for 6, return 0	6	(0,0)	diameter=2	6(0) leaf
14	Back to 3, max1=1 (from 6)	3	(1,0)	diameter=2	3(1) with child 6(0)
15	Visit child 7 of 3	7	(0,0)	diameter=2	3(1) -> 7(0)
16	No children for 7, return 0	7	(0,0)	diameter=2	7(0) leaf
17	Back to 3, max2=1 (from 7)	3	(1,1)	diameter=2	3(1) with children 6(0),7(0)
18	Update diameter = max(2,1+1)=2	3	(1,1)	diameter=2	Diameter unchanged at node 3
19	Return max1=1 to node 1	3	(1,1)	diameter=2	Return depth 1 from 3
20	Back to 1, max1=1 (from 2)	1	(1,0)	diameter=2	1(1) with child 2(1)
21	max2=1 (from 3)	1	(1,1)	diameter=2	1(1) with children 2(1),3(1)
22	Update diameter = max(2,1+1)=2	1	(1,1)	diameter=2	Diameter unchanged at node 1
23	Return max1=1	1	(1,1)	diameter=2	DFS complete
24	End	-	-	diameter=2	Final diameter is 2

💡 DFS completes after visiting all nodes; diameter is maximum sum of two largest depths found.

Variable Tracker

Variable	Start	After Step 5	After Step 8	After Step 14	After Step 17	After Step 21	Final
diameter	0	0	2	2	2	2	2
max1 (current node)	0	1 (node 2)	1 (node 2)	1 (node 3)	1 (node 3)	1 (node 1)	1 (node 1)
max2 (current node)	0	0	1 (node 2)	0	1 (node 3)	1 (node 1)	1 (node 1)

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 by combining the two longest paths from its children. See execution_table rows 8 and 21 where diameter updates use max1 + max2.

Why do we add 1 to the child's depth when returning from DFS?

Adding 1 accounts for the edge between the current node and its child, representing the path length. This is shown in execution_table row 5 where depth = dfs(child) + 1.

Why do we ignore the parent node during DFS traversal?

To avoid revisiting the node we came from and prevent infinite loops. This is shown in the code snippet and reflected in the traversal steps in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the diameter value after processing node 2?

A 2

B 1

C 0

D 3

💡 Hint

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

At which step does the diameter first update to 3?

A Step 18

B Step 21

C Step 24

D Step 9

💡 Hint

Look for the first 'Diameter Update' value of 3 in execution_table.

If the tree had an extra child with depth 3 at node 3, how would max1 change at step 14?

A max1 would remain 1

B max1 would become 3

C max1 would become 2

D max1 would become 4

💡 Hint

max1 tracks the largest depth from children; see variable_tracker for max1 changes.

Concept Snapshot

DP on Trees Diameter:
- Use DFS twice or DP to find longest path.
- Track two largest depths (max1, max2) at each node.
- Diameter = max sum of max1 + max2 over all nodes.
- Return max1 to parent for depth calculation.
- Ignore parent in DFS to avoid cycles.

Full Transcript

To find the diameter of a tree using DP, we run a DFS from any node. At each node, we calculate the two longest depths from its children, called max1 and max2. The diameter is updated as the maximum sum of these two depths at any node. We add 1 to the child's depth to account for the edge connecting them. We ignore the parent node during DFS to prevent revisiting. After visiting all nodes, the global diameter variable holds the longest path length in the tree.

Practice

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

easy

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

B. The number of nodes in the tree

C. The height of the tree from the root

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the definition of tree diameter

   The diameter is defined as the longest path between any two nodes in a tree, not necessarily passing through 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 path lengths.

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path in tree [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 must pass through root

2. Which of the following is the correct way to declare a vector of vectors to represent an adjacency list for a tree in C++?

easy

A. std::vector<int> adj[n];

B. std::vector adj(n);

C. std::vector adj(n, std::vector<int>());

D. std::vector adj(n);

Solution

1. Step 1: Understand vector of vectors syntax

   Correct syntax uses std::vector adj(n); to create n empty vectors.

2. Step 2: Check other options for errors

   std::vector<int> adj[n]; uses array of vectors (valid but less modern), C misses template arguments, D misses template parameters.

3. Final Answer:

   std::vector adj(n); -> Option B

4. Quick Check:

   Correct vector of vectors syntax = std::vector adj(n); [OK]

Hint: Use std::vector adj(n); for adjacency list [OK]

Common Mistakes:

• Missing template parameters in vector
• Using C-style arrays instead of vectors
• Incorrect initialization syntax

3. Consider the following C++ code snippet to find the diameter of a tree using DFS and DP. What will be the output if the tree edges are: (0-1), (1-2), (1-3)?

std::vector adj(4);
adj[0].push_back(1); adj[1].push_back(0);
adj[1].push_back(2); adj[2].push_back(1);
adj[1].push_back(3); adj[3].push_back(1);

int diameter = 0;

int dfs(int node, int parent, const std::vector& adj, int& diameter) {
    int max1 = 0, max2 = 0;
    for (int child : adj[node]) {
        if (child == parent) continue;
        int height = dfs(child, node, adj, diameter) + 1;
        if (height > max1) {
            max2 = max1;
            max1 = height;
        } else if (height > max2) {
            max2 = height;
        }
    }
    diameter = std::max(diameter, max1 + max2);
    return max1;
}

dfs(0, -1, adj, diameter);
std::cout << diameter << std::endl;

medium

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Understand the tree structure and DFS traversal

   The tree edges form a structure: 0-1 connected, 1 connected to 2 and 3. The longest path is from node 2 to node 3 through 1, length 2 edges.

2. Step 2: Calculate diameter from DFS logic

   DFS calculates max1 and max2 heights from children. For node 1, max1=1 (to 2), max2=1 (to 3), so diameter = max(0,1+1)=2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Longest path length = 2 edges [OK]

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

Common Mistakes:

• Counting nodes instead of edges for diameter
• Not updating diameter correctly
• Confusing parent and child in DFS

4. The following code attempts to compute the diameter of a tree but produces incorrect results. What is the main bug?

int dfs(int node, int parent, const std::vector& adj, int& diameter) {
    int maxHeight = 0;
    for (int child : adj[node]) {
        if (child == parent) continue;
        int height = dfs(child, node, adj, diameter) + 1;
        if (height > maxHeight) {
            maxHeight = height;
            diameter = std::max(diameter, maxHeight);
        }
    }
    return maxHeight;
}

medium

A. DFS does not return any value

B. Parent node is not skipped in DFS

C. Diameter is updated only with maxHeight, missing sum of two heights

D. Height is not incremented correctly

Solution

1. Step 1: Analyze diameter update logic

   The code updates diameter only with maxHeight, which is the longest single path from current node, but diameter requires sum of two longest paths through the node.

2. Step 2: Identify missing second longest path

   Without tracking two longest heights, the code misses paths passing through the node combining two children, leading to incorrect diameter.

3. Final Answer:

   Diameter is updated only with maxHeight, missing sum of two heights -> Option C

4. Quick Check:

   Diameter needs sum of two longest child heights [OK]

Hint: Track two longest heights to update diameter correctly [OK]

Common Mistakes:

• Updating diameter with only one child's height
• Not skipping parent node in DFS
• Forgetting to increment height by 1

5. Given a tree with 6 nodes and edges: (0-1), (1-2), (1-3), (3-4), (4-5), what is the diameter of the tree? Use the DP on Trees approach where diameter is the longest path between any two nodes.

hard

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Visualize the tree and identify longest path

   The tree edges form paths: 0-1-3-4-5 and 2 connected to 1. The longest path is from node 2 to node 5 passing through 1,3,4 with length 5 edges.

2. Step 2: Calculate diameter using DP on Trees logic

   At node 1, two longest child heights are 1 (to 2) and 3 (to 5). Diameter = max(diameter, 1+3) = 4, but the longest path is from 2 to 5 which is 4 edges plus 1 edge from 0 to 1 is not part of longest path. Actually, the longest path is from node 2 to node 5 passing through 1,3,4 with length 5 edges.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Longest path length = 5 edges [OK]

Hint: Diameter = sum of two longest child heights at a node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring one branch in longest path
• Miscounting edges in path