Height of Binary Tree in DSA Rust - Execution Trace

Concept Flow - Height of Binary Tree

Start at root node

↓

Is node None?

Yes→Return 0

No↓

Recursively find height of left subtree

↓

Recursively find height of right subtree

↓

Calculate max(left_height, right_height) + 1

↓

Return height for current node

↓

Repeat until root returns final height

Start at the root, recursively find heights of left and right subtrees, then return the larger height plus one until the entire tree's height is found.

Execution Sample

DSA Rust

fn height(node: &Option<Box<TreeNode>>) -> i32 {
    match node {
        None => 0,
        Some(n) => 1 + i32::max(height(&n.left), height(&n.right)),
    }
}

This function calculates the height of a binary tree by recursively checking left and right children.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Returned	Visual State
1	Start at root	1	-	-	-	1 / \ 2 3 / 4
2	Go left from 1	2	-	-	-	2 / 4
3	Go left from 2	4	-	-	-	4
4	Left child of 4 is None	None	0	-	0	None
5	Right child of 4 is None	None	-	0	0	None
6	Calculate height at 4	4	0	0	1	4
7	Right child of 2 is None	None	-	0	0	None
8	Calculate height at 2	2	1	0	2	2 / 4
9	Go right from 1	3	-	-	-	3
10	Left child of 3 is None	None	0	-	0	None
11	Right child of 3 is None	None	-	0	0	None
12	Calculate height at 3	3	0	0	1	3
13	Calculate height at 1	1	2	1	3	1 / \ 2 3 / 4
14	Return final height	1	2	1	3	Tree height is 3

💡 All nodes visited, height calculated bottom-up, final height returned at root

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	After Step 13	Final
Current Node	1	4	4	2	3	1	1
Left Height	-	0	0	1	0	2	2
Right Height	-	-	-	0	0	1	1
Height Returned	-	0	1	2	1	3	3

Key Moments - 3 Insights

Why do we return 0 when the node is None?

Because a None node means no tree exists there, so its height is zero. This is shown in steps 4 and 5 where left and right children of leaf nodes return 0.

Why do we add 1 after taking max of left and right heights?

The +1 accounts for the current node itself. Steps 6, 8, 12, and 13 show height calculation as 1 + max(left, right).

How does recursion ensure all nodes are visited?

The function calls itself on left and right children until None is reached, as seen in steps 2-5 and 9-11, ensuring all nodes are processed.

Visual Quiz - 3 Questions

Look at the execution table, what is the height returned at node 2 (step 8)?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Height Returned' column at step 8 in the execution_table.

At which step does the recursion return height 1 for a leaf node?

A Step 4

B Step 6

C Step 12

D Step 13

💡 Hint

Look for the first time 'Height Returned' is 1 for a node in the execution_table.

If the right child of node 1 had a left child, how would the height at node 3 change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would become 0

💡 Hint

Consider how adding a child affects the max(left_height, right_height) in the height calculation.

Concept Snapshot

Height of Binary Tree:
- Height is max depth from root to leaf
- Base case: None node height = 0
- Recursive case: height = 1 + max(left_height, right_height)
- Returns 0 for empty tree
- Uses post-order traversal (left, right, root)

Full Transcript

The height of a binary tree is found by starting at the root and recursively finding the height of the left and right subtrees. If a node is None, it returns 0. For each node, the height is 1 plus the maximum height of its left and right children. This process continues until the root returns the final height. The execution table shows each step visiting nodes, calculating left and right heights, and returning the height. Key moments clarify why None returns 0, why we add 1, and how recursion visits all nodes. The visual quiz tests understanding of height values at specific steps and effects of adding nodes.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. 1

B. Undefined

C. 2

D. 0

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of edges on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 0 edges.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Single node tree height = 0 [OK]

Hint: Height counts edges from root to deepest leaf [OK]

Common Mistakes:

• Confusing height with number of nodes
• Thinking empty tree has height 1
• Assuming height starts at 1

2. Which of the following Rust function signatures correctly represents a function to calculate the height of a binary tree node defined as struct Node { left: Option, right: Option }?

easy

A. fn height(node: &Option) -> usize

B. fn height(node: Node) -> usize

C. fn height(node: &Node) -> usize

D. fn height(node: Option<Node>) -> usize

Solution

1. Step 1: Analyze parameter types

   The tree nodes are wrapped in Option to allow nullability and heap allocation.

2. Step 2: Choose correct reference type

   Passing a reference to Option (&Option) avoids moving ownership and allows checking for None.

3. Final Answer:

   fn height(node: &Option) -> usize -> Option A

4. Quick Check:

   Use &Option to handle nullable nodes safely [OK]

Hint: Use &Option to avoid ownership issues [OK]

Common Mistakes:

• Passing Node by value moves ownership
• Using Option<Node> instead of Option
• Using &Node misses None case

3. Given the following Rust code, what is the printed height of the binary tree?

struct Node {
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn height(node: &Option<Box<Node>>) -> usize {
    match node {
        None => 0,
        Some(n) => 1 + height(n.left).max(height(n.right)),
    }
}

fn main() {
    let leaf = Node { left: None, right: None };
    let left_child = Node { left: Some(Box::new(leaf)), right: None };
    let root = Some(Box::new(Node { left: Some(Box::new(left_child)), right: None }));
    println!("{}", height(&root));
}

medium

A. 0

B. 2

C. 3

D. 1

Solution

1. Step 1: Trace leaf node height

   The leaf node has no children, so height = 1 (0 + 1).

2. Step 2: Trace left_child height

   Left_child has left = leaf (height 1), right = None (height 0), so height = 1 + max(1,0) = 2.

3. Step 3: Trace root height

   Root has left = left_child (height 2), right = None (height 0), so height = 1 + max(2,0) = 3.

4. Final Answer:

   3 -> Option C

5. Quick Check:

   Height counts nodes on longest path = 3 [OK]

Hint: Count nodes from root to deepest leaf recursively [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring None children
• Misreading recursive calls

4. Identify the bug in this Rust function to calculate binary tree height and select the correct fix:

fn height(node: Option<Box<Node>>) -> usize {
    if node.is_none() {
        return 0;
    }
    let n = node.unwrap();
    1 + height(n.left).max(height(n.right))
}

medium

A. Replace unwrap() with expect() to handle errors

B. Change parameter to &Option<Box<Node>> and use references to avoid moving ownership

C. Return 1 instead of 0 when node is None

D. Use Box<Node> instead of Option<Box<Node>> as parameter

Solution

1. Step 1: Identify ownership issue

   Calling unwrap() moves ownership of node, making recursive calls invalid as ownership is lost.

2. Step 2: Fix by using references

   Changing parameter to &Option<Box<Node>> allows borrowing without moving ownership, enabling safe recursion.

3. Final Answer:

   Change parameter to &Option<Box<Node>> and use references to avoid moving ownership -> Option B

4. Quick Check:

   Use references to prevent ownership errors in recursion [OK]

Hint: Use references to avoid moving nodes in recursion [OK]

Common Mistakes:

• Using unwrap() moves ownership
• Ignoring ownership rules
• Changing return values incorrectly

5. You want to find the height of a binary tree but only have access to a vector of edges representing parent-child relationships as tuples (parent, child). Which approach correctly computes the height of the tree in Rust?

hard

A. Build the tree nodes from edges, then recursively compute height from root node

B. Count the number of edges in the vector and return that as height

C. Use the number of unique nodes as the height

D. Return the maximum child value from edges as height

Solution

1. Step 1: Understand input format

   The vector of edges gives parent-child pairs but no direct tree structure.

2. Step 2: Build tree structure

   Construct nodes and link children to parents to form the tree, identifying the root (node with no parent).

3. Step 3: Compute height recursively

   Starting from root node, recursively calculate height by finding max height of left and right subtrees.

4. Final Answer:

   Build the tree nodes from edges, then recursively compute height from root node -> Option A

5. Quick Check:

   Build tree first, then compute height recursively [OK]

Hint: Convert edges to tree nodes before height calculation [OK]

Common Mistakes:

• Using edge count as height
• Ignoring tree structure
• Assuming max child value equals height