Diameter of Binary Tree in DSA Rust

Mental Model

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

Analogy: Imagine a tree as a network of roads connecting towns. The diameter is the longest possible trip you can take between two towns without retracing your steps.

      1
     / \
    2   3
   / \
  4   5

Here, arrows show parent to child connections.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Find the longest path between any two nodes in the tree

Step 1: Calculate height of node 4 (leaf)

Node 4 height = 0

Why: Leaf nodes have height zero, base case for recursion

Step 2: Calculate height of node 5 (leaf)

Node 5 height = 0

Why: Leaf nodes have height zero, base case for recursion

Step 3: Calculate height of node 2 as max height of children + 1 = 1

Node 2 height = 1

Why: Height is longest path down to leaf

Step 4: Calculate height of node 3 (leaf)

Node 3 height = 0

Why: Leaf node height is zero

Step 5: Calculate diameter at node 2 as left height + right height = 0 + 0 = 0

Diameter at node 2 = 0

Why: Longest path through node 2 connects leaves 4 and 5, edges count is 2 but diameter counts edges between nodes

Step 6: Calculate diameter at node 1 as max of left diameter, right diameter, left height + right height = max(0,0,1+0)=1

Diameter at node 1 = 1

Why: Longest path passes through root from leaf 4 to leaf 3

Result:

Diameter = 3 (path: 4 -> 2 -> 1 -> 3)

Annotated Code

DSA Rust

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

#[derive(Debug, Clone)]
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 {
    max_diameter: i32,
}

impl Solution {
    fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut sol = Solution { max_diameter: 0 };
        sol.depth(&root);
        sol.max_diameter
    }

    fn depth(&mut self, node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(n) = node {
            let left_depth = self.depth(&n.borrow().left);
            let right_depth = self.depth(&n.borrow().right);
            // Update max diameter if path through this node is longer
            if left_depth + right_depth > self.max_diameter {
                self.max_diameter = left_depth + right_depth;
            }
            // Return height of this node
            1 + left_depth.max(right_depth)
        } else {
            0
        }
    }
}

fn main() {
    // Build tree:
    //      1
    //     / \
    //    2   3
    //   / \
    //  4   5
    let root = TreeNode::new(1);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);

    root.borrow_mut().left = Some(node2.clone());
    root.borrow_mut().right = Some(node3.clone());
    node2.borrow_mut().left = Some(node4);
    node2.borrow_mut().right = Some(node5);

    let diameter = Solution::diameter_of_binary_tree(Some(root));
    println!("Diameter of the binary tree is: {}", diameter);
}

let left_depth = self.depth(&n.borrow().left);

Recursively find height of left subtree

let right_depth = self.depth(&n.borrow().right);

Recursively find height of right subtree

if left_depth + right_depth > self.max_diameter { self.max_diameter = left_depth + right_depth; }

Update max diameter if current node's path is longer

1 + left_depth.max(right_depth)

Return height of current node as 1 plus max child height

Output

Diameter of the binary tree is: 3

Complexity Analysis

Time: O(n) because each node is visited once during depth calculation

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach might compute height repeatedly causing O(n^2) time; this approach computes height and diameter in one pass

Edge Cases

Empty tree

Diameter is 0 because there are no nodes

DSA Rust

if let Some(n) = node { ... } else { 0 }

Single node tree

Diameter is 0 because no edges exist

DSA Rust

if let Some(n) = node { ... } else { 0 }

Linear tree (all nodes have only one child)

Diameter equals number of edges in the longest path (number of nodes - 1)

DSA Rust

self.max_diameter = left_depth + right_depth

When to Use This Pattern

When asked for longest path between any two nodes in a tree, use diameter pattern by combining heights of left and right subtrees at each node.

Common Mistakes

Mistake: Calculating diameter as height of left subtree plus height of right subtree plus 2 instead of plus 0
Fix: Diameter counts edges, so sum left and right heights (which count edges) without adding extra 2

Mistake: Recomputing height multiple times causing inefficient O(n^2) time
Fix: Use a single recursive function that returns height and updates diameter simultaneously

Summary

Finds the longest path between any two nodes in a binary tree.

Use when you need the maximum distance between two nodes in a tree structure.

The diameter is the largest sum of left and right subtree heights at any node.

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