Height of Binary Tree in DSA Rust

Mental Model

The height of a binary tree is the longest path from the root to any leaf node. We find it by checking how deep the tree goes.

Analogy: Imagine a family tree where height is how many generations you count from the oldest ancestor down to the youngest descendant.

    1
   / \
  2   3
 / 
4  
↑ root

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4 (left child), 1 -> 3 (right child)

Goal: Find the height of the tree, which is the longest path from root to leaf

Step 1: Start at root node 1, check left subtree height

1 -> [curr->2] -> 4 -> null
Right subtree: 3 -> null

Why: We need to find height of left subtree first to compare

Step 2: At node 2, check left subtree height

2 -> [curr->4] -> null
No right child

Why: Go deeper to find leaf nodes

Step 3: At node 4, no children, height is 1

4 -> null (leaf)

Why: Leaf node height is 1

Step 4: Back to node 2, left height is 1, right height is 0, so height is 1 + max(1,0) = 2

2 -> 4 -> null

Why: Height is 1 + max height of the subtrees

Step 5: Check right subtree of root 1: node 3 has no children, height is 1

3 -> null (leaf)

Why: Leaf node height is 1

Step 6: At root 1, left height is 2, right height is 1, so height is 1 + max(2,1) = 3

1 -> 2 -> 4 -> null and 1 -> 3 -> null

Why: Height is longest path from root to leaf

Result:

Height = 3

Annotated Code

DSA Rust

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

#[derive(Debug)]
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 }))
    }
}

fn height(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if root.is_none() {
        return 0; // empty tree has height 0
    }
    let node = root.unwrap();
    let left_height = height(node.borrow().left.clone()); // height of left subtree
    let right_height = height(node.borrow().right.clone()); // height of right subtree
    1 + std::cmp::max(left_height, right_height) // height is 1 + max of subtrees
}

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

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

    let h = height(Some(root));
    println!("Height = {}", h);
}

if root.is_none() { return 0; }

return 0 for empty subtree base case

let left_height = height(node.borrow().left.clone());

recursively find height of left subtree

let right_height = height(node.borrow().right.clone());

recursively find height of right subtree

1 + std::cmp::max(left_height, right_height)

height is 1 plus max height of subtrees

Output

Height = 3

Complexity Analysis

Time: O(n) because we visit every node once to calculate height

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

vs Alternative: Iterative methods exist but recursion is simpler and clear for height calculation

Edge Cases

Empty tree

Returns height 0 as base case

DSA Rust

if root.is_none() { return 0; }

Single node tree

Returns height 1 since root is also leaf

DSA Rust

1 + std::cmp::max(left_height, right_height)

Unbalanced tree (all nodes on one side)

Height equals number of nodes in longest path

DSA Rust

1 + std::cmp::max(left_height, right_height)

When to Use This Pattern

When a problem asks for the longest path from root to leaf or depth of a tree, use the height calculation pattern by recursively checking subtree heights.

Common Mistakes

Mistake: Returning 0 for leaf nodes instead of 1
Fix: Return 0 only for empty nodes; leaf nodes have height 1

Mistake: Not cloning Rc pointers before recursive calls causing borrow errors
Fix: Use .clone() on Rc pointers before recursion to avoid borrow conflicts

Summary

Calculates the longest path from root to any leaf node in a binary tree.

Use when you need to know how deep or tall a tree is.

The height is 1 plus the maximum height of its left and right subtrees.

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