Diameter of Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Diameter Calculation on a Simple Binary Tree

What is the output of the following Rust code that calculates the diameter of a binary tree?

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

struct Solution;

impl Solution {
    fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn depth(node: &Option<Rc<RefCell<TreeNode>>>, max_diameter: &mut i32) -> i32 {
            if let Some(n) = node {
                let left_depth = depth(&n.borrow().left, max_diameter);
                let right_depth = depth(&n.borrow().right, max_diameter);
                *max_diameter = (*max_diameter).max(left_depth + right_depth);
                1 + left_depth.max(right_depth)
            } else {
                0
            }
        }
        let mut max_diameter = 0;
        depth(&root, &mut max_diameter);
        max_diameter
    }
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().right = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(4));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(5));

    let diameter = Solution::diameter_of_binary_tree(Some(root));
    println!("{}", diameter);
}

A 5

B 3

C 4

D 2

💡 Hint

Think about the longest path between any two nodes in the tree, which may pass through the root.

The diameter is the length of the longest path between any two nodes. Here, the longest path is from node 4 to node 3 passing through nodes 2 and 1, which has length 3 edges.

❓ Predict Output

intermediate

Diameter Output for a Skewed Binary Tree

What will be printed by this Rust program computing the diameter of a skewed binary tree?

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

struct Solution;

impl Solution {
    fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn depth(node: &Option<Rc<RefCell<TreeNode>>>, max_diameter: &mut i32) -> i32 {
            if let Some(n) = node {
                let left_depth = depth(&n.borrow().left, max_diameter);
                let right_depth = depth(&n.borrow().right, max_diameter);
                *max_diameter = (*max_diameter).max(left_depth + right_depth);
                1 + left_depth.max(right_depth)
            } else {
                0
            }
        }
        let mut max_diameter = 0;
        depth(&root, &mut max_diameter);
        max_diameter
    }
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().right = Some(TreeNode::new(2));
    root.borrow_mut().right.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(3));
    root.borrow_mut().right.as_ref().unwrap().borrow_mut().right.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(4));

    let diameter = Solution::diameter_of_binary_tree(Some(root));
    println!("{}", diameter);
}

A 3

B 4

C 1

D 0

💡 Hint

In a skewed tree, the diameter equals the number of edges in the longest path.

The tree is skewed to the right with nodes 1 -> 2 -> 3 -> 4. The longest path is from node 1 to node 4, which has 3 edges.

🔧 Debug

advanced

Identify the Runtime Error in Diameter Calculation

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

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

struct Solution;

impl Solution {
    fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn depth(node: &Option<Rc<RefCell<TreeNode>>>, max_diameter: &mut i32) -> i32 {
            if let Some(n) = node {
                let left_depth = depth(&n.borrow().left, max_diameter);
                let right_depth = depth(&n.borrow().right, max_diameter);
                *max_diameter = (*max_diameter).max(left_depth + right_depth);
                1 + left_depth.max(right_depth)
            } else {
                0
            }
        }
        let mut max_diameter = 0;
        depth(&root, &mut max_diameter);
        max_diameter
    }
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().left = Some(TreeNode::new(3));

    let diameter = Solution::diameter_of_binary_tree(Some(root));
    println!("{}", diameter);
}

A Output is 1

B Runtime panic due to multiple mutable borrows

C Compilation error: cannot borrow immutable as mutable

D No error, output is 2

💡 Hint

Check how left child is assigned twice and what happens to the first assignment.

Assigning left child twice overwrites the first child. No mutable borrow conflicts occur because borrows are scoped. The diameter is 2 from node 2 or 3 to 1.

🧠 Conceptual

advanced

Understanding Diameter Calculation Logic

In the diameter calculation of a binary tree, why do we update the maximum diameter with the sum of left and right subtree depths at each node?

A Because the diameter is the maximum depth of either left or right subtree

B Because the diameter is always the sum of the heights of left and right subtrees

C Because the longest path may pass through the current node connecting left and right subtrees

D Because the diameter counts the number of nodes in the tree

💡 Hint

Think about the longest path that might cross the root of a subtree.

The diameter is the longest path between any two nodes. This path can pass through the current node, connecting the deepest nodes in the left and right subtrees. Hence, we consider left_depth + right_depth at each node.

🚀 Application

expert

Calculate Diameter for a Complex Tree Structure

Given the following binary tree structure, what is the diameter printed by the Rust program?

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

struct Solution;

impl Solution {
    fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn depth(node: &Option<Rc<RefCell<TreeNode>>>, max_diameter: &mut i32) -> i32 {
            if let Some(n) = node {
                let left_depth = depth(&n.borrow().left, max_diameter);
                let right_depth = depth(&n.borrow().right, max_diameter);
                *max_diameter = (*max_diameter).max(left_depth + right_depth);
                1 + left_depth.max(right_depth)
            } else {
                0
            }
        }
        let mut max_diameter = 0;
        depth(&root, &mut max_diameter);
        max_diameter
    }
}

fn main() {
    let root = TreeNode::new(1);
    let left = TreeNode::new(2);
    let right = TreeNode::new(3);
    let left_left = TreeNode::new(4);
    let left_right = TreeNode::new(5);
    let right_right = TreeNode::new(6);
    let right_right_left = TreeNode::new(7);

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());
    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right);
    right.borrow_mut().right = Some(right_right.clone());
    right_right.borrow_mut().left = Some(right_right_left);

    let diameter = Solution::diameter_of_binary_tree(Some(root));
    println!("{}", diameter);
}

A 5

B 6

C 4

D 7

💡 Hint

Trace the longest path between two nodes, which may pass through the root or deeper nodes.

The longest path is from node 4 to node 7 passing through nodes 2, 1, 3, and 6. This path has 5 edges, so the diameter is 5.

Practice

1. What does the diameter of a binary tree represent?

easy

A. The height of the tree

B. The total number of nodes in the tree

C. The number of leaf nodes

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

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, which may or may not pass through the root.

2. Step 2: Differentiate from height and node count

   Height is the longest path from root to leaf, leaf count is number of leaves, and total nodes count all nodes, so they are different.

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path between nodes [OK]

Hint: Diameter is longest path, not height or node count [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of edges
• Assuming diameter always passes through root

2. Which Rust function signature correctly represents a function to compute the diameter of a binary tree node defined as struct TreeNode { val: i32, left: Option, right: Option }?

easy

A. fn diameter_of_binary_tree(root: Option) -> i32

B. fn diameter_of_binary_tree(root: TreeNode) -> i32

C. fn diameter_of_binary_tree(root: &TreeNode) -> i32

D. fn diameter_of_binary_tree(root: Option<TreeNode>) -> i32

Solution

1. Step 1: Understand Rust ownership and Option usage

   The tree nodes are wrapped in Option to allow for empty children and heap allocation.

2. Step 2: Match function signature to tree root type

   The root is an Option, so the function must accept this type to handle empty trees and ownership.

3. Final Answer:

   fn diameter_of_binary_tree(root: Option) -> i32 -> Option A

4. Quick Check:

   Use Option for tree root [OK]

Hint: Use Option for nullable tree nodes [OK]

Common Mistakes:

• Using TreeNode directly without Option or Box
• Using references without handling ownership
• Using Option<TreeNode> instead of Option

3. Given the following Rust code snippet, what is the output printed?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

fn diameter_of_binary_tree(root: &Option) -> i32 {
    fn depth(node: &Option, max_diameter: &mut i32) -> i32 {
        if let Some(n) = node {
            let left_depth = depth(&n.left, max_diameter);
            let right_depth = depth(&n.right, max_diameter);
            *max_diameter = (*max_diameter).max(left_depth + right_depth);
            1 + left_depth.max(right_depth)
        } else {
            0
        }
    }
    let mut max_diameter = 0;
    depth(root, &mut max_diameter);
    max_diameter
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: None,
        })),
    }));
    println!("{}", diameter_of_binary_tree(&root));
}

medium

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Calculate depths of left and right subtrees

   Left child (val 2) and right child (val 3) have depth 1 each (no children).

2. Step 2: Calculate diameter at root

   Diameter is max of previous and left_depth + right_depth = 1 + 1 = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Diameter = left depth + right depth = 2 [OK]

Hint: Diameter = sum of left and right subtree depths [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with diameter
• Forgetting to update max diameter

4. Identify the bug in this Rust function to compute the diameter of a binary tree:

fn diameter_of_binary_tree(root: &Option) -> i32 {
    fn depth(node: &Option, max_diameter: &mut i32) -> i32 {
        if node.is_none() {
            return 0;
        }
        let left_depth = depth(&node.as_ref().unwrap().left, max_diameter);
        let right_depth = depth(&node.as_ref().unwrap().right, max_diameter);
        max_diameter = &mut left_depth + right_depth;  // Bug here
        1 + left_depth.max(right_depth)
    }
    let mut max_diameter = 0;
    depth(root, &mut max_diameter);
    max_diameter
}

medium

A. Incorrect assignment to max_diameter; should use max() to update

B. Missing base case for empty node

C. Wrong return type of depth function

D. Using unwrap() without checking Option

Solution

1. Step 1: Analyze max_diameter update line

   The line 'max_diameter = &mut left_depth + right_depth;' tries to assign sum to a mutable reference incorrectly.

2. Step 2: Correct way to update max_diameter

   Should update max_diameter by comparing current max and sum: '*max_diameter = (*max_diameter).max(left_depth + right_depth);'

3. Final Answer:

   Incorrect assignment to max_diameter; should use max() to update -> Option A

4. Quick Check:

   Update max_diameter with max() function [OK]

Hint: Use max() to update max_diameter, not direct assignment [OK]

Common Mistakes:

• Assigning to reference instead of dereferencing
• Not updating max_diameter correctly
• Ignoring Option safety but not main bug here

5. You want to find the diameter of a binary tree but also return the path nodes forming that diameter. Which approach best extends the diameter calculation in Rust?

hard

A. Store all node values in a vector and find longest path after traversal

B. Modify depth function to return (depth, path) and update max path when diameter increases

C. Calculate diameter first, then do a separate DFS to find path

D. Use a queue to store nodes and find diameter iteratively

Solution

1. Step 1: Understand diameter with path tracking

   To get the path, depth function must return both depth and path nodes so we can track the longest path.

2. Step 2: Update max path when diameter increases

   When a longer diameter is found, update stored path combining left and right subtree paths plus current node.

3. Final Answer:

   Modify depth function to return (depth, path) and update max path when diameter increases -> Option B

4. Quick Check:

   Return depth and path together to track diameter path [OK]

Hint: Return depth and path tuple to track diameter nodes [OK]

Common Mistakes:

• Trying to find path after diameter without tracking
• Using iterative queue approach which is complex here
• Storing all nodes wastes memory and is inefficient