Check if Binary Tree is Balanced in DSA Rust - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: Imagine you are building a system that manages a family tree. To keep the tree easy to search and update, you want to make sure it is balanced. A balanced tree means no branch is much longer than another, so finding family members is quick.

🎯 Goal: You will create a binary tree structure, add a helper variable, write a function to check if the tree is balanced, and finally print the result.

📋 What You'll Learn

Create a binary tree node struct called TreeNode with value, left, and right fields

Create a sample binary tree with exact values and structure

Add a helper function height to calculate the height of a subtree

Write a function is_balanced that returns true if the tree is balanced, false otherwise

Print the result of is_balanced for the sample tree

💡 Why This Matters

🌍 Real World

Balanced binary trees are used in databases and file systems to keep data organized for fast searching and updating.

💼 Career

Understanding tree balance is important for software engineers working with data structures, algorithms, and performance optimization.

1

Create the Binary Tree Node and Sample Tree

Create a struct called TreeNode with fields value: i32, left: Option>, and right: Option>. Then create a variable called root representing this tree:

1
/ \ 2 3
/
4

Use Some(Box::new(TreeNode { ... })) to build the tree exactly as shown.

DSA Rust

# Define TreeNode struct and create the root tree
# Your code here

Hint

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

2

Add a Helper Function to Calculate Height

Add a function called height that takes a reference to Option> and returns an i32. It should return 0 if the node is None. Otherwise, it returns 1 plus the maximum height of the left and right children.

DSA Rust

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

fn height(node: &Option>) -> i32 {
    // Your code here
}

fn main() {
    let root = Some(Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode {
                value: 4,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            value: 3,
            left: None,
            right: None,
        })),
    }));
}

Hint

Use recursion to find the height of left and right children, then add 1 for the current node.

3

Write the Function to Check if Tree is Balanced

Write a function called is_balanced that takes a reference to Option> and returns a bool. It should return true if the tree is balanced, meaning the height difference between left and right children is at most 1 for every node. Use the height function to get heights and check balance recursively.

DSA Rust

struct TreeNode {
    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 is_balanced(node: &Option>) -> bool {
    // Your code here
}

fn main() {
    let root = Some(Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode {
                value: 4,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            value: 3,
            left: None,
            right: None,
        })),
    }));
}

Hint

Check the height difference at current node and recursively check left and right subtrees.

4

Print if the Tree is Balanced

Write a println! statement to print the result of is_balanced(&root). It should print true or false depending on the tree balance.

DSA Rust

struct TreeNode {
    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 is_balanced(node: &Option>) -> bool {
    match node {
        None => true,
        Some(n) => {
            let left_height = height(&n.left);
            let right_height = height(&n.right);
            let diff = (left_height - right_height).abs();
            diff <= 1 && is_balanced(&n.left) && is_balanced(&n.right)
        }
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode {
                value: 4,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            value: 3,
            left: None,
            right: None,
        })),
    }));

    // Your code here
}

Hint

Use println!("{}", is_balanced(&root)) to print the result.

Practice

1. What does it mean for a binary tree to be balanced?

easy

A. The height difference between left and right subtrees of every node is at most 1

B. All nodes have two children

C. The tree has the same number of nodes on left and right

D. The tree is sorted in ascending order

Solution

1. Step 1: Understand balance condition

   A balanced binary tree means for every node, the height difference between its left and right subtrees is at most 1.

2. Step 2: Eliminate incorrect options

   All nodes having two children describes a full tree. Equal number of nodes in subtrees does not define balance. Sorted order defines a BST. None match the balance definition.

3. Final Answer:

   The height difference between left and right subtrees of every node is at most 1 -> Option A

4. Quick Check:

   Balance means height difference ≤ 1 [OK]

Hint: Balance means subtree heights differ by no more than 1 [OK]

Common Mistakes:

• Confusing balanced with complete or full tree
• Thinking balance means equal number of nodes
• Assuming sorted order means balanced

2. Which Rust function signature correctly represents a function that checks if a binary tree is balanced?

easy

A. fn is_balanced(root: Option) -> bool

B. fn is_balanced(root: Option<TreeNode>) -> bool

C. fn is_balanced(root: &Option) -> bool

D. fn is_balanced(root: TreeNode) -> bool

Solution

1. Step 1: Understand Rust ownership and references

   Binary trees are usually represented with Option<Box<TreeNode>>. Passing by reference (&Option<Box<TreeNode>>) avoids moving ownership.

2. Step 2: Analyze the signatures

   Passing Option<Box<TreeNode>> moves ownership. Option<TreeNode> is invalid due to infinite size. TreeNode directly ignores None roots. &Option<Box<TreeNode>> correctly borrows the tree.

3. Final Answer:

   fn is_balanced(root: &Option<Box<TreeNode>>) -> bool -> Option C

4. Quick Check:

   Use reference to Option<Box<TreeNode>> [OK]

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

Common Mistakes:

• Passing TreeNode directly instead of boxed option
• Not using references causing ownership errors
• Using Option<TreeNode> instead of Option

3. Given the following Rust code snippet, what will be the output?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

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

fn is_balanced(root: &Option) -> bool {
    match root {
        None => true,
        Some(n) => {
            let lh = height(&n.left);
            let rh = height(&n.right);
            (lh - rh).abs() <= 1 && is_balanced(&n.left) && is_balanced(&n.right)
        }
    }
}

fn main() {
    let tree = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: None,
            right: None,
        })),
        right: None,
    }));
    println!("{}", is_balanced(&tree));
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze tree structure

   The tree has root 1, left child 2, and no right child. Left subtree height = 1, right subtree height = 0.

2. Step 2: Check balance condition

   Height difference is 1 which is ≤ 1. Both left and right subtrees are leaves or None, so balanced. So overall tree is balanced.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Height difference ≤ 1 means balanced [OK]

Hint: Check subtree heights and recursive balance [OK]

Common Mistakes:

• Assuming missing right child means unbalanced
• Confusing height calculation logic
• Ignoring recursive balance checks

4. Identify the bug in this Rust function that checks if a binary tree is balanced:

fn is_balanced(root: &Option) -> bool {
    if root.is_none() {
        return true;
    }
    let node = root.as_ref().unwrap();
    let lh = height(&node.left);
    let rh = height(&node.right);
    if (lh - rh).abs() > 1 {
        return false;
    }
    is_balanced(&node.left);
    is_balanced(&node.right);
    true
}

medium

A. Using unwrap() causes panic on None

B. Incorrect height calculation function used

C. Wrong type used for root parameter

D. Missing return of recursive calls results in ignoring their results

Solution

1. Step 1: Review recursive calls

   The recursive calls to is_balanced(&node.left) and is_balanced(&node.right) are made but their results are not used or returned.

2. Step 2: Understand impact

   Ignoring recursive results means function always returns true if root is not None and height difference ≤ 1, missing unbalanced deeper nodes.

3. Final Answer:

   Missing return of recursive calls results in ignoring their results -> Option D

4. Quick Check:

   Return recursive results to propagate balance status [OK]

Hint: Always return recursive call results in boolean checks [OK]

Common Mistakes:

• Not returning recursive call results
• Assuming unwrap() always safe without check
• Confusing parameter types

5. You want to optimize the balance check to avoid repeated height calculations in Rust. Which approach is best?

hard

A. Calculate height first, then check balance separately in another traversal

B. Calculate height and balance in one recursive function returning Option<i32> height or None if unbalanced

C. Use a global variable to store heights of nodes

D. Only check balance at root node

Solution

1. Step 1: Understand repeated height calculation problem

   Calculating height separately for each node causes repeated work, increasing time complexity.

2. Step 2: Use combined recursive function

   Returning height if balanced or None if unbalanced lets us stop early and avoid repeated height calls.

3. Step 3: Analyze other options

   Separate height and balance traversals is less efficient. Global variables introduce unsafe state. Root-only check misses subtree imbalances.

4. Final Answer:

   Calculate height and balance in one recursive function returning Option<i32> height or None if unbalanced -> Option B

5. Quick Check:

   Combine height and balance check for efficiency [OK]

Hint: Return height or None to detect imbalance early [OK]

Common Mistakes:

• Doing separate height and balance traversals
• Using global variables for tree state
• Checking balance only at root