DP on Trees Diameter of Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Diameter Calculation on a Simple Tree

What is the output of the following Rust code that calculates the diameter of a tree represented as adjacency lists?

DSA Rust

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

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

A 4

B 3

C 2

D 5

💡 Hint

Think about the longest path between any two nodes in the tree.

The diameter is the longest path between any two nodes. Here, the longest path is from node 3 to node 2 or node 4 to node 2, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding Diameter Calculation Logic

In the DP approach to find the diameter of a tree, why do we keep track of the two longest distances from a node to its children?

A Because the diameter might pass through the node connecting the two longest child paths

B Because the sum of all child distances gives the diameter

C Because the shortest path between children defines the diameter

D Because only one longest path from a child is needed to find the diameter

💡 Hint

Think about the longest path that goes through a node connecting two subtrees.

The diameter can be the longest path passing through a node, which is the sum of the two longest child paths from that node.

🔧 Debug

advanced

Identify the Error in Diameter Calculation Code

What error will the following Rust code produce when calculating the diameter of a tree?

DSA Rust

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

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

A The code outputs 0 instead of 2

B The code runs correctly and outputs 2

C Stack overflow due to infinite recursion

D Compilation error due to missing return statement

💡 Hint

Check how distances are calculated and returned in recursion.

The code forgets to add 1 to the distance returned by recursive calls, so all distances remain 0 and it outputs 0 instead of 2.

❓ Predict Output

advanced

Output of Diameter Calculation on a Star-Shaped Tree

What is the output of the following Rust code that calculates the diameter of a star-shaped tree with 5 nodes?

DSA Rust

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

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

A 1

B 3

C 4

D 2

💡 Hint

The diameter in a star tree is the longest path between two leaves through the center.

The longest path is between any two leaves through the center node 0, which is 2 edges long.

🚀 Application

expert

Maximum Diameter After Adding One Edge

Given a tree with N nodes, you can add exactly one edge between any two nodes to create a cycle. Which option correctly describes how to find the maximum possible diameter after adding this edge?

A Add an edge between the two nodes with the largest depths from the root to increase the diameter

B Add an edge between the two nodes that are endpoints of the current diameter to increase the diameter by 1

C Add an edge between any two nodes to create a cycle; the diameter remains the same as the original tree

D Add an edge between two nodes that are farthest apart in the tree to create a cycle and recalculate the diameter considering the cycle

💡 Hint

Think about how adding an edge creates a cycle and how that affects longest paths.

Adding an edge between any two nodes creates a cycle, but the longest path (diameter) remains the same as the original tree since the original paths are still available and new paths using the edge are shorter.

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