Diameter of Binary Tree in DSA Rust - Build from Scratch

Diameter of Binary Tree

📖 Scenario: Imagine you are working with a family tree represented as a binary tree. You want to find the longest path between any two family members in this tree. This longest path is called the diameter of the binary tree.

🎯 Goal: Build a Rust program that creates a binary tree, calculates its diameter (the longest path between any two nodes), and prints the diameter value.

📋 What You'll Learn

Create a binary tree using a TreeNode struct with val, left, and right fields

Add a helper variable to track the maximum diameter found

Write a recursive function to calculate the height of each node and update the diameter

Print the final diameter value

💡 Why This Matters

🌍 Real World

Finding the diameter of a binary tree helps in network design, family trees, and understanding longest communication paths.

💼 Career

This concept is useful for software engineers working with tree data structures, algorithms, and performance optimization.

1

Create the binary tree structure

Define a TreeNode struct with val: i32, left: Option>, and right: Option>. Then create a binary tree variable called root with this exact structure: root value 1, left child value 2, right child value 3, left child of 2 is 4, right child of 2 is 5.

DSA Rust

# Define TreeNode struct and create the binary tree variable root
# Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Add a variable to track the maximum diameter

Inside main, create a mutable variable called max_diameter and set it to 0. This will keep track of the longest path found so far.

DSA Rust

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

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
    }));
    // Create max_diameter variable here
    // Your code here
}

Hint

Use let mut max_diameter = 0; inside main.

3

Write a recursive function to calculate height and update diameter

Define a function called height that takes node: &Option> and a mutable reference to max_diameter: &mut i32. It returns an i32 height. The function should recursively calculate the height of left and right children, update max_diameter with the sum of left and right heights if larger, and return the max height plus one.

DSA Rust

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

fn height(node: &Option>, max_diameter: &mut i32) -> i32 {
    // Your code here
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
    }));
    let mut max_diameter = 0;
    // Call height function here
    // Your code here
}

Hint

Use recursion to get left and right heights. Update max_diameter if left_height + right_height is bigger.

4

Print the diameter of the binary tree

Add a println! statement inside main to print the text "Diameter of the binary tree is: " followed by the value of max_diameter.

DSA Rust

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

fn height(node: &Option>, max_diameter: &mut i32) -> i32 {
    if let Some(n) = node {
        let left_height = height(&n.left, max_diameter);
        let right_height = height(&n.right, max_diameter);
        let diameter = left_height + right_height;
        if diameter > *max_diameter {
            *max_diameter = diameter;
        }
        return 1 + std::cmp::max(left_height, right_height);
    } else {
        0
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
    }));
    let mut max_diameter = 0;
    height(&root, &mut max_diameter);
    // Print the diameter below
    // Your code here
}

Hint

Use println!("Diameter of the binary tree is: {}", max_diameter); to show the result.

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