DP on Trees Diameter of Tree in DSA Rust - 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 = 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

We run DFS twice to find the farthest nodes and use DP to track max depths, updating diameter as max sum of two depths at each node.

Execution Sample

DSA Rust

fn dfs(node: usize, parent: usize, graph: &Vec<Vec<usize>>, dp: &mut Vec<usize>, diameter: &mut usize) {
    let mut max1 = 0;
    let mut max2 = 0;
    for &child in &graph[node] {
        if child != parent {
            dfs(child, node, graph, dp, diameter);
            let child_depth = 1 + dp[child];
            if child_depth > max1 {
                max2 = max1;
                max1 = child_depth;
            } else if child_depth > max2 {
                max2 = child_depth;
            }
        }
    }
    *diameter = std::cmp::max(*diameter, max1 + max2);
    dp[node] = max1;
}

This DFS function calculates max depths from each node and updates the diameter using DP on tree.

Execution Table

Step	Operation	Node Visited	Max Depths (max1, max2)	Diameter Update	Visual State
1	Start DFS at node 0	0	(0, 0)	Diameter = 0	0 |--1 | |--3 | |--4 |--2
2	Visit child 1 of 0	1	(0, 0)	Diameter = 0	0 |--1 | |--3 | |--4 |--2
3	Visit child 3 of 1	3	(0, 0)	Diameter = 0	0 |--1 | |--3 | |--4 |--2
4	Return from 3 to 1	1	(1, 0)	Diameter = 0	Depth at 3 = 0, max1=1 at 1
5	Visit child 4 of 1	4	(0, 0)	Diameter = 0	0 |--1 | |--3 | |--4 |--2
6	Return from 4 to 1	1	(1, 1)	Diameter = 2	Depths at 1: max1=1, max2=1, diameter updated to 2
7	Return from 1 to 0	0	(2, 0)	Diameter = 2	Depth at 1 = 2, max1=2 at 0
8	Visit child 2 of 0	2	(0, 0)	Diameter = 2	0 |--1 | |--3 | |--4 |--2
9	Return from 2 to 0	0	(2, 1)	Diameter = 3	Depth at 2 = 1, max2=1 at 0, diameter updated to 3
10	DFS complete	-	-	Diameter = 3	Final diameter is 3

💡 DFS completes after visiting all nodes, diameter is max sum of two max depths at root.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 9	Final
max1	0	1	1	2	2	2
max2	0	0	1	0	1	1
diameter	0	0	2	2	3	3
dp[node]	0	0 (dp[3]=0)	1 (dp[1]=1)	2 (dp[1]=2)	0 (dp[2]=0)	2 (dp[0]=2)

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 steps 6 and 9 where diameter updates use sum of max1 and 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 condition 'if child != parent' in the code and reflected in the traversal steps.

How is the diameter updated during DFS?

At each node, after computing max1 and max2, diameter is updated if max1 + max2 is greater than current diameter. This happens at steps 6 and 9.

Visual Quiz - 3 Questions

Look at the execution table, what is the diameter after step 6?

A 0

B 2

C 3

D 1

💡 Hint

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

At which step does the diameter become 3?

A Step 9

B Step 8

C Step 7

D Step 10

💡 Hint

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

If we did not track max2 (second max depth), what would happen to the diameter calculation?

A Diameter would be overestimated

B Diameter would remain correct

C Diameter would be underestimated

D DFS would not terminate

💡 Hint

Refer to key_moments about why two max depths are needed for correct diameter.

Concept Snapshot

DP on Trees Diameter:
- Use DFS to find max depths from each node
- Track two largest depths (max1, max2) per node
- Update diameter as max(diameter, max1 + max2)
- Ignore parent node to avoid cycles
- Diameter = longest path between any two nodes

Full Transcript

To find the diameter of a tree using DP, we run DFS from any node to find the farthest node A. Then run DFS from A to find farthest node B. The distance between A and B is the diameter. During DFS, we use DP to store the maximum depths of subtrees. 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. We avoid revisiting the parent node to prevent cycles. The final diameter is the longest path between any two nodes in the tree.

Practice

1. What does the diameter of a tree represent in the context of DP on Trees?

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 sum of all edge weights in the tree

Solution

1. Step 1: Understand the definition of tree diameter

   The diameter is the longest path between any two nodes, not just from the root or sum of edges.

2. Step 2: Differentiate from other tree properties

   Height is from root to leaf, sum of edges is total weight, number of nodes is size, none equal diameter.

3. Final Answer:

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

4. Quick Check:

   Diameter = Longest path [OK]

Hint: Diameter = longest path between any two nodes [OK]

Common Mistakes:

• Confusing diameter with tree height
• Thinking diameter is total nodes count
• Assuming diameter is sum of all edges

2. Which Rust syntax correctly declares a recursive function to compute the diameter of a tree represented as adjacency list Vec?

easy

A. fn diameter(node: usize, parent: usize, graph: &mut Vec) -> usize { ... }

B. fn diameter(node: usize, graph: Vec) -> usize { ... }

C. fn diameter(node: usize, parent: usize, graph: &Vec) -> usize { ... }

D. fn diameter(&self, node: usize, parent: usize) -> usize { ... }

Solution

1. Step 1: Identify correct parameter passing for graph

   Graph should be passed by reference (&Vec) to avoid copying large data.

2. Step 2: Include parent parameter to avoid revisiting parent node

   Parent node is needed to prevent cycles in undirected tree traversal.

3. Final Answer:

   fn diameter(node: usize, parent: usize, graph: &Vec) -> usize { ... } -> Option C

4. Quick Check:

   Pass graph by reference and track parent [OK]

Hint: Pass graph as &Vec and track parent node [OK]

Common Mistakes:

• Passing graph by value causing performance issues
• Missing parent parameter causing infinite recursion
• Using &mut when mutation is not needed

3. Given the following Rust code snippet to compute the diameter of a tree, what is the printed output?

fn dfs(node: usize, parent: usize, graph: &Vec, max_diameter: &mut usize) -> usize {
    let mut max1 = 0;
    let mut max2 = 0;
    for &child in &graph[node] {
        if child == parent { continue; }
        let height = dfs(child, node, graph, max_diameter);
        if height > max1 {
            max2 = max1;
            max1 = height;
        } else if height > max2 {
            max2 = height;
        }
    }
    *max_diameter = (*max_diameter).max(max1 + max2);
    max1 + 1
}

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![0, 3, 4],
        vec![0],
        vec![1],
        vec![1]
    ];
    let mut max_diameter = 0;
    dfs(0, usize::MAX, &graph, &mut max_diameter);
    println!("{}", max_diameter);
}

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace DFS heights from leaves

   Leaves 2, 3, 4 return height 1; node 1 gets max1=1, max2=1; node 0 gets max1=2 (from node 1), max2=1 (from node 2).

2. Step 2: Calculate max diameter updates

   At node 1, max_diameter = max(0,1+1)=2; at node 0, max_diameter = max(2,2+1)=3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Sum two largest subtree heights at each node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Not updating max_diameter correctly
• Ignoring parent to avoid revisiting

4. Identify the bug in this Rust function computing tree diameter and select the fix:

fn dfs(node: usize, graph: &Vec, max_diameter: &mut usize) -> usize {
    let mut max1 = 0;
    let mut max2 = 0;
    for &child in &graph[node] {
        let height = dfs(child, graph, max_diameter);
        if height > max1 {
            max2 = max1;
            max1 = height;
        } else if height > max2 {
            max2 = height;
        }
    }
    *max_diameter = (*max_diameter).max(max1 + max2);
    max1 + 1
}

medium

A. Initialize max1 and max2 to 1 instead of 0

B. Add a parent parameter to avoid revisiting the parent node

C. Change max_diameter to return instead of using mutable reference

D. Remove max2 variable as it is unnecessary

Solution

1. Step 1: Identify infinite recursion cause

   Without parent tracking, dfs revisits parent causing infinite recursion or stack overflow.

2. Step 2: Fix by adding parent parameter

   Pass parent node to skip revisiting it in children loop, preventing cycles.

3. Final Answer:

   Add a parent parameter to avoid revisiting the parent node -> Option B

4. Quick Check:

   Parent tracking prevents infinite recursion [OK]

Hint: Always track parent node in undirected tree DFS [OK]

Common Mistakes:

• Not passing parent causing infinite recursion
• Misusing mutable references for max_diameter
• Incorrect initialization of max heights

5. You want to find the diameter of a weighted tree where edges have weights. Which modification to the DP on Trees diameter algorithm is correct?

hard

A. Ignore weights and compute diameter as number of edges only

B. Sum all edge weights and divide by two to get diameter

C. Use BFS twice without any DP or recursion

D. Store and propagate the maximum weighted path length instead of just height counts

Solution

1. Step 1: Understand weighted tree diameter difference

   Diameter must consider edge weights, so heights become max weighted path lengths.

2. Step 2: Modify DP to accumulate weights

   Instead of counting edges, add edge weights when computing subtree heights and update max diameter accordingly.

3. Final Answer:

   Store and propagate the maximum weighted path length instead of just height counts -> Option D

4. Quick Check:

   Weighted diameter needs weighted path sums [OK]

Hint: Accumulate edge weights in DP for weighted diameter [OK]

Common Mistakes:

• Ignoring weights leads to wrong diameter
• Using BFS without weights misses weighted paths
• Incorrect formula dividing total weights