Height of Binary Tree in DSA Rust - Build from Scratch

Height of Binary Tree

📖 Scenario: Imagine you have a family tree showing generations of ancestors. You want to find out how many generations tall this family tree is.

🎯 Goal: Build a simple binary tree in Rust and write code to find its height (the number of levels from the root to the deepest leaf).

📋 What You'll Learn

Create a binary tree with exactly 3 nodes: root, left child, and right child

Add a variable to hold the height of the tree

Write a recursive function to calculate the height of the binary tree

Print the height of the binary tree

💡 Why This Matters

🌍 Real World

Binary trees are used in many places like organizing data, searching quickly, and representing hierarchical information such as family trees or file systems.

💼 Career

Understanding binary trees and recursion is essential for software development roles involving data structures, algorithms, and system design.

1

Create a simple binary tree

Create a struct called Node with fields value: i32, left: Option, and right: Option. Then create a variable called root which is a Node with value 1, left child with value 2, and right child with value 3. Use Box and Option as shown.

DSA Rust

// Define struct Node and create root node with left and right children
// Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Add a variable to hold the height

Inside the main function, create a mutable variable called height and set it to 0. This will store the height of the binary tree.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn main() {
    let root = Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
    };
    // Create a mutable variable height and set it to 0
    // Your code here
}

Hint

Use let mut height = 0; inside main.

3

Write a recursive function to find height

Write a function called height that takes a reference to an Option<Box<Node>> and returns an i32. It should return 0 if the node is None. Otherwise, it should return 1 plus the maximum height of the left and right children by calling itself recursively.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

// Write a recursive function height to find the height of the tree
fn height(node: &Option>) -> i32 {
    // Your code here
}

fn main() {
    let root = Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
    };
    let mut height = 0;
}

Hint

Use match on node. Return 0 if None. Otherwise, return 1 plus the max of recursive calls on left and right.

4

Calculate and print the height

In the main function, set height to the result of calling height(&Some(Box::new(root))). Then print the height using println!("Height of the tree: {}", height).

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn height(node: &Option>) -> i32 {
    match node {
        None => 0,
        Some(n) => {
            let left_height = height(&n.left);
            let right_height = height(&n.right);
            1 + std::cmp::max(left_height, right_height)
        }
    }
}

fn main() {
    let root = Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
    };
    let mut height = 0;
    // Set height by calling height function on root wrapped in Some(Box::new())
    // Print the height
    // Your code here
}

Hint

Call height(&Some(Box::new(root))) and assign to height. Then print it with println!("Height of the tree: {}", height).

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