Diameter of Binary Tree in DSA Rust - Execution Trace

Concept Flow - Diameter of Binary Tree

Start at root node

↓

Compute left subtree height

↓

Compute right subtree height

↓

Calculate diameter through current node = left height + right height

↓

Update max diameter if current is larger

↓

Return height of current node = max(left, right) + 1

↓

Repeat for left and right children recursively

↓

Final max diameter stored after full traversal

The flow shows how we recursively find heights of left and right subtrees, update the diameter at each node, and return heights up the tree.

Execution Sample

DSA Rust

fn diameter_of_binary_tree(root: Option<&Box<TreeNode>>) -> i32 {
    fn height(node: Option<&Box<TreeNode>>, max_diameter: &mut i32) -> i32 {
        if let Some(n) = node {
            let left = height(n.left.as_ref(), max_diameter);
            let right = height(n.right.as_ref(), max_diameter);
            *max_diameter = (*max_diameter).max(left + right);
            return 1 + left.max(right);
        }
        0
    }

    let mut max_diameter = 0;
    height(root, &mut max_diameter);
    max_diameter
}

This Rust function calculates the diameter of a binary tree by recursively computing subtree heights and updating the maximum diameter found.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Diameter Update	Max Diameter	Height Returned	Visual State
1	Visit root	1	?	?	No	0	?	1 / \ 2 3 / 4
2	Visit left child	2	?	?	No	0	?	2 / 4
3	Visit left-left child	4	0	0	No	0	1	4 (leaf)
4	Return to node 2	2	1	0	Update diameter = 1	1	2	2 / 4
5	Visit right child	3	0	0	No	1	1	3 (leaf)
6	Return to root	1	2	1	Update diameter = 3	3	3	1 / \ 2 3 /
7	Traversal complete	N/A	N/A	N/A	Final max diameter = 3	3	N/A	Final tree with diameter 3

💡 Traversal ends after visiting all nodes; max diameter found is 3.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
max_diameter	0	0	1	1	3	3
height(node 4)	N/A	1	1	1	1	1
height(node 2)	N/A	N/A	2	2	2	2
height(node 3)	N/A	N/A	N/A	1	1	1
height(root 1)	N/A	N/A	N/A	N/A	3	3

Key Moments - 3 Insights

Why do we add left and right heights to update the diameter?

Because the diameter at a node is the longest path through it, which equals left subtree height plus right subtree height (see Step 4 and Step 6 in execution_table).

Why do we return max(left, right) + 1 as height?

Height is the longest path from current node down to a leaf, so we take the larger height of children plus one for current node (see Height Returned column in execution_table).

Why is max_diameter updated only after visiting both children?

Because we need both left and right heights to calculate diameter through current node, so update happens after recursive calls return (see Steps 4 and 6).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the max_diameter value?

A 2

B 0

C 1

D 3

💡 Hint

Check the 'Max Diameter' column at Step 4 in execution_table.

At which step does the diameter update to 3?

A Step 3

B Step 6

C Step 4

D Step 7

💡 Hint

Look for the largest diameter update in the 'Diameter Update' and 'Max Diameter' columns.

If the left subtree height of root was 3 instead of 2, how would max_diameter change at Step 6?

A It would become 4

B It would remain 3

C It would become 5

D It would become 6

💡 Hint

Diameter at root = left height + right height; check variable_tracker for heights.

Concept Snapshot

Diameter of Binary Tree:
- Diameter = longest path between any two nodes
- At each node, diameter = left height + right height
- Use recursion to get heights and update max diameter
- Return height = max(left, right) + 1
- Final max diameter after full traversal is answer

Full Transcript

The diameter of a binary tree is the longest path between any two nodes. We find it by recursively calculating the height of left and right subtrees at each node. The diameter through a node is the sum of left and right subtree heights. We keep track of the maximum diameter found so far. The height returned for each node is one plus the maximum height of its children. After visiting all nodes, the maximum diameter recorded is the diameter of the tree.

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