Check if Binary Tree is Balanced in DSA Rust - Deep Dive

Overview - Check if Binary Tree is Balanced

What is it?

A binary tree is balanced if the height difference between the left and right subtrees of every node is at most one. This means no part of the tree is much deeper than another, keeping operations efficient. Checking if a binary tree is balanced involves verifying this height difference condition for every node. It helps ensure the tree remains fast for searching and inserting.

Why it matters

Without checking balance, a binary tree can become very uneven, like a tall skinny tree. This slows down operations like search, insert, and delete, making them as slow as going through a list. Balanced trees keep these operations fast, which is crucial for performance in many applications like databases and file systems. Knowing if a tree is balanced helps decide if rebalancing is needed.

Where it fits

Before this, you should understand what a binary tree is and how to measure tree height. After this, you can learn about self-balancing trees like AVL or Red-Black trees that maintain balance automatically.

Mental Model

Core Idea

A binary tree is balanced if no node's left and right subtrees differ in height by more than one.

Think of it like...

Imagine a seesaw with two kids sitting on each side. If one side is much heavier (taller subtree), the seesaw tips and is unbalanced. Balanced means both sides are nearly equal in weight (height).

       Root
      /    \
   Left   Right
   Subtree Subtree
    (h1)    (h2)

Balanced if |h1 - h2| ≤ 1 for every node

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Height

Concept: Learn how to find the height of a binary tree node recursively.

The height of a node is the number of edges on the longest path from that node down to a leaf. For a leaf node, height is 0. For other nodes, height is 1 plus the maximum height of its left and right children. Rust example: ```rust fn height(node: &Option>) -> i32 { match node { None => -1, // empty subtree has height -1 Some(n) => 1 + std::cmp::max(height(&n.left), height(&n.right)), } } ``` This function returns the height of the tree rooted at `node`.

Result

Calling height on a tree returns the longest path length from root to leaf.

Understanding height is key because balance depends on comparing subtree heights.

2

Foundation

Defining Balanced Binary Tree Condition

Concept: Introduce the balance condition based on subtree heights difference.

A node is balanced if the height difference between its left and right subtrees is at most 1. The whole tree is balanced if every node satisfies this. Formally: |height(left_subtree) - height(right_subtree)| ≤ 1 If any node violates this, the tree is unbalanced.

Result

You can check balance by comparing heights at each node.

Balance is a local property checked at every node, not just the root.

3

Intermediate

Naive Balance Check Using Separate Height Calls

🤔Before reading on: Do you think calling height separately for each node is efficient or slow? Commit to your answer.

Concept: Check balance by computing heights separately for each node's subtrees, then verify the difference.

We write a function that for each node: 1. Calls height on left subtree. 2. Calls height on right subtree. 3. Checks if difference ≤ 1. 4. Recursively checks left and right subtrees are balanced. Rust code: ```rust fn is_balanced_naive(node: &Option>) -> bool { match node { None => true, Some(n) => { let left_height = height(&n.left); let right_height = height(&n.right); (left_height - right_height).abs() <= 1 && is_balanced_naive(&n.left) && is_balanced_naive(&n.right) } } } ``` This works but calls height many times repeatedly.

Result

Returns true if tree is balanced, false otherwise, but inefficient for large trees.

Repeated height calls cause many redundant calculations, slowing down the check.

4

Intermediate

Optimized Single-Pass Balance Check

🤔Before reading on: Can you guess how to check balance and height in one pass? Commit to your idea.

Concept: Combine height calculation and balance check in one recursive function to avoid repeated work.

We create a helper function that returns: - The height of the subtree if balanced. - A special value (e.g., -1) if unbalanced. Algorithm: 1. Recursively get left subtree height. 2. If left is unbalanced (-1), return -1. 3. Recursively get right subtree height. 4. If right is unbalanced (-1), return -1. 5. If height difference > 1, return -1. 6. Else return max height + 1. Rust code: ```rust fn check_balance(node: &Option>) -> i32 { match node { None => 0, Some(n) => { let left_height = check_balance(&n.left); if left_height == -1 { return -1; } let right_height = check_balance(&n.right); if right_height == -1 { return -1; } if (left_height - right_height).abs() > 1 { -1 } else { 1 + std::cmp::max(left_height, right_height) } } } } fn is_balanced(node: &Option>) -> bool { check_balance(node) != -1 } ``` This checks balance and height in one traversal.

Result

Returns true if balanced, false if not, with much better performance.

Combining checks prevents repeated height calculations, making the algorithm efficient.

5

Advanced

Handling Edge Cases and Empty Trees

🤔Before reading on: Is an empty tree balanced? Commit to yes or no.

Concept: Understand how empty trees and single-node trees are balanced by definition.

An empty tree (no nodes) is balanced because there are no nodes to violate balance. A single-node tree is balanced because both left and right subtrees are empty (height -1 or 0 depending on definition), so difference is 0. The code handles these naturally: - `None` returns height 0 or -1. - Balance check returns true. This ensures the algorithm works for all tree shapes.

Result

Empty and single-node trees return balanced = true.

Recognizing base cases prevents errors and ensures correctness for all inputs.

6

Expert

Surprising Performance Impact of Naive Approach

🤔Before reading on: Do you think naive balance check runs in linear or quadratic time? Commit to your answer.

Concept: Analyze time complexity difference between naive and optimized methods and why naive can be very slow.

Naive approach calls height for every node, and height itself is O(n) in worst case. For each node, height is recalculated for subtrees repeatedly, leading to O(n^2) time. Optimized approach visits each node once, doing O(1) work per node, total O(n). In large trees, naive method can be very slow and impractical. This explains why combining height and balance check is critical in real systems.

Result

Naive method: O(n^2) time; optimized method: O(n) time.

Understanding complexity differences guides writing efficient code and avoiding performance traps.

Under the Hood

The optimized balance check uses a post-order traversal: it first checks left and right subtrees, then uses their heights to decide balance at the current node. Returning -1 as a sentinel signals unbalanced subtrees early, allowing the function to stop further checks. This reduces redundant height calculations and avoids unnecessary work.

Why designed this way?

Originally, balance was checked by separate height calls, but this was inefficient. The combined approach was designed to improve performance by merging height and balance checks into one pass. The sentinel value (-1) is a simple way to propagate failure up the recursion stack without extra data structures.

          check_balance(node)
                 │
        ┌────────┴────────┐
   check_balance(left)  check_balance(right)
        │                    │
   returns height or -1  returns height or -1
        │                    │
        └─────┬──────────────┘
              │
    if either is -1 return -1
    else if |left - right| > 1 return -1
    else return max(left, right) + 1

Myth Busters - 3 Common Misconceptions

Quick: Is an empty tree considered balanced? Commit to yes or no.

Common Belief: An empty tree is not balanced because it has no nodes.

Reality: An empty tree is balanced by definition since there are no nodes to violate balance.

Why it matters: Misunderstanding this can cause incorrect code that fails on empty inputs or crashes.

Quick: Does checking balance by calling height separately for each node run efficiently? Commit to yes or no.

Common Belief: Calling height separately for each node is efficient enough for balance checking.

Reality: This naive approach is inefficient and can lead to O(n^2) time complexity on large trees.

Why it matters: Using naive methods in production can cause severe performance issues and slowdowns.

Quick: If a node's left subtree is balanced and right subtree is balanced, is the node always balanced? Commit to yes or no.

Common Belief: If both subtrees are balanced, the node must be balanced too.

Reality: The node can still be unbalanced if the height difference between subtrees is more than one.

Why it matters: Assuming subtree balance implies node balance leads to incorrect results.

Expert Zone

1

The sentinel value (-1) used to indicate unbalance is a clever trick that avoids extra boolean flags or complex return types.

2

In some implementations, height is defined as number of nodes instead of edges; understanding this difference is crucial when adapting algorithms.

3

Early stopping when unbalance is detected saves time, especially in large trees with deep unbalanced branches.

When NOT to use

This check is only for static trees or one-time checks. For dynamic trees with frequent inserts/deletes, use self-balancing trees like AVL or Red-Black trees that maintain balance automatically.

Production Patterns

In real systems, balance checks are used before rebalancing operations or to validate tree integrity. The optimized single-pass method is standard in libraries and frameworks to ensure performance.

Connections

AVL Trees

Builds-on

Understanding balance checking is foundational to AVL trees, which automatically rebalance after insertions and deletions to maintain this property.

Divide and Conquer Algorithms

Same pattern

The recursive height and balance check uses divide and conquer by solving subproblems (subtrees) and combining results, a common algorithmic pattern.

Structural Engineering

Analogous principle

Just like balanced trees avoid tipping over, structural engineers ensure buildings have balanced load distribution to prevent collapse.

Common Pitfalls

#1 Recomputing height for every node separately causes slow performance.

Wrong approach:

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

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

Correct approach:

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

fn is_balanced(node: &Option>) -> bool {
check_balance(node) != -1
}

Root cause:

Not combining height and balance checks leads to repeated height calculations.

#2 Assuming empty tree is unbalanced and returning false.

Wrong approach:

fn is_balanced(node: &Option>) -> bool {
match node {
None => false, // incorrect
Some(_) => true,
}
}

Correct approach:

fn is_balanced(node: &Option>) -> bool {
match node {
None => true, // empty tree is balanced
Some(_) => true,
}
}

Root cause:

Misunderstanding base case for empty trees.

Key Takeaways

A binary tree is balanced if every node's left and right subtrees differ in height by no more than one.

Naive balance checks that call height repeatedly are inefficient and can cause slowdowns on large trees.

Combining height calculation and balance checking in one recursive pass improves performance to linear time.

Empty trees and single-node trees are balanced by definition and must be handled correctly.

Understanding balance checking is essential for advanced tree structures like AVL trees and for writing efficient tree algorithms.

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