Diameter of Binary Tree in DSA Rust - Time & Space Complexity

Time Complexity: Diameter of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the diameter of a binary tree changes as the tree grows.

Specifically, how does the work increase when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

    let mut diameter = 0;
    depth(root, &mut diameter);
    diameter
}
    

This code calculates the diameter of a binary tree by recursively finding the depth of each node's left and right children and updating the maximum path length found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to visit each node once.
• How many times: Each node is visited exactly one time during the depth calculation.

How Execution Grows With Input

As the number of nodes (n) increases, the function visits each node once, so the total work grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the diameter grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The diameter calculation is O(n²) because it checks paths between all pairs of nodes."

[OK] Correct: The code visits each node once and calculates depths on the way back, so it does not repeatedly check all pairs, avoiding extra work.

Interview Connect

Understanding this linear time approach shows you can efficiently solve tree problems by combining recursion and tracking results during traversal.

Self-Check

"What if the tree was skewed (like a linked list)? How would the time complexity change?"

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