Why Check if Binary Tree is Balanced in DSA Rust?

The Big Idea

What if you could instantly know if your tree is balanced without counting every branch twice?

The Scenario

Imagine you have a family tree drawn on paper. You want to check if the tree looks balanced, meaning no side is much taller than the other. Doing this by measuring each branch by hand is tiring and confusing.

The Problem

Manually checking each branch's height and comparing takes a lot of time and mistakes happen easily. You might miss some branches or count wrong, making the whole check unreliable.

The Solution

Using a smart method, you can check the tree's balance by looking at each branch just once, quickly finding if any side is too tall compared to the other. This saves time and avoids errors.

Before vs After

✗ Before

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

// Then check balance by comparing heights separately

✓ After

fn check_balance(node: &Option<Box<Node>>) -> (bool, i32) {
    if node.is_none() { return (true, 0); }
    let (left_balanced, left_height) = check_balance(&node.as_ref().unwrap().left);
    let (right_balanced, right_height) = check_balance(&node.as_ref().unwrap().right);
    let balanced = left_balanced && right_balanced && (left_height - right_height).abs() <= 1;
    (balanced, left_height.max(right_height) + 1)
}

What It Enables

This lets you quickly and reliably know if a tree is balanced, which helps keep data organized and fast to search.

Real Life Example

When building a phone contact list, a balanced tree ensures you find a contact quickly without waiting long because one side of the list is too long.

Key Takeaways

Manual height checks are slow and error-prone.

Smart recursive checks combine height and balance in one step.

Balanced trees keep data fast to access and reliable.

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