Diameter of Binary Tree in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the TreeNode struct with optional left and right children.

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>, 
    right: Option<Box<TreeNode>>[1]
}

Drag options to blanks, or click blank then click option'

A:

B;

C.

D,

Attempts:

3 left

💡 Hint

Common Mistakes

Using semicolon instead of comma after struct fields.

Missing comma causing syntax errors.

In Rust struct fields are separated by commas. So a comma is needed after the right field declaration.

2fill in blank

medium

Complete the code to calculate the maximum depth of a binary tree node recursively.

DSA Rust

fn max_depth(node: &Option<Box<TreeNode>>) -> i32 {
    match node {
        None => 0,
        Some(n) => 1 + std::cmp::max(max_depth(&n.left), [1])
    }
}

Drag options to blanks, or click blank then click option'

Amax_depth(n.right)

Bmax_depth(&n.right)

Cmax_depth(n.left)

Dmax_depth(&n)

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting to use a reference causing type errors.

Calling max_depth on the wrong child.

We must recursively call max_depth on the right child with a reference, so &n.right is correct.

3fill in blank

hard

Complete the return statement in the diameter_helper function to return the correct height.

DSA Rust

fn diameter_helper(node: &Option<Box<TreeNode>>, diameter: &mut i32) -> i32 {
    match node {
        None => 0,
        Some(n) => {
            let left = diameter_helper(&n.left, diameter);
            let right = diameter_helper(&n.right, diameter);
            *diameter = std::cmp::max(*diameter, left + right);
            1 + [1]
        }
    }
}

Drag options to blanks, or click blank then click option'

Astd::cmp::max(left, right)

Bleft - right

Cleft + right

Dleft * right

Attempts:

3 left

💡 Hint

Common Mistakes

Returning sum instead of max causing incorrect height.

Returning product or difference causing wrong results.

The function returns the height of the node, which is max of left and right subtree heights plus one (already added outside).

4fill in blank

hard

Fill both blanks to complete the diameter_of_binary_tree function that initializes diameter and calls helper.

DSA Rust

fn diameter_of_binary_tree(root: Option<Box<TreeNode>>) -> i32 {
    let mut diameter = [1];
    diameter_helper(&root, &mut diameter);
    [2]
}

Drag options to blanks, or click blank then click option'

A0

Bdiameter

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing diameter to 1 instead of 0.

Returning wrong variable or nothing.

Diameter starts at 0 and after helper call, we return the diameter value.

5fill in blank

hard

Fill all three blanks to correctly update diameter and return height in diameter_helper.

DSA Rust

fn diameter_helper(node: &Option<Box<TreeNode>>, diameter: &mut i32) -> i32 {
    match node {
        None => 0,
        Some(n) => {
            let left = diameter_helper(&n.left, diameter);
            let right = diameter_helper(&n.right, diameter);
            *diameter = std::cmp::max(*diameter, [1]);
            [2] + [3]
        }
    }
}

Drag options to blanks, or click blank then click option'

Aleft + right

Bstd::cmp::max(left, right)

Cright

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Updating diameter with incorrect values.

Returning sum instead of max plus one for height.

Diameter is updated with left + right path length. Height returned is std::cmp::max(left, right) + 1.

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