Check if Binary Tree is Balanced in DSA Rust

Mental Model

A balanced binary tree means no branch is much deeper than its sibling branches. We check if every node's left and right subtrees differ in height by at most one.

Analogy: Imagine a tree with branches on both sides. If one side is much longer than the other, the tree might fall. We want to make sure both sides grow evenly, like balanced arms holding a weight.

      1
     / \
    2   3
   / 
  4  

Balanced tree example where left and right subtree heights differ by 1 or less.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4

Goal: Determine if the tree is balanced by checking height differences at every node

Step 1: Check height of node 4 (leaf)

Node 4: height = 0 (no children)

Why: Leaf nodes have height 0, base case for height calculation

Step 2: Check height of node 2 by checking left child 4 and right child null

Node 2: left height = 0, right height = -1 (null), difference = 1

Why: Calculate height difference to verify balance at node 2

Step 3: Check height of node 3 (leaf)

Node 3: height = 0 (no children)

Why: Leaf node height is 0

Step 4: Check height of root node 1 by left subtree height 1 and right subtree height 0

Node 1: left height = 1, right height = 0, difference = 1

Why: Calculate height difference at root to confirm balance

Step 5: Confirm all nodes have height difference ≤ 1, tree is balanced

Tree is balanced

Why: No node violates the balance condition

Result:

1 -> balanced

Annotated Code

DSA Rust

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

#[derive(Debug, Clone)]
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 check_height(node: &Option<Rc<RefCell<TreeNode>>>) -> Result<i32, ()> {
    if let Some(n) = node {
        let n_borrow = n.borrow();
        let left_height = check_height(&n_borrow.left)?;
        let right_height = check_height(&n_borrow.right)?;
        if (left_height - right_height).abs() > 1 {
            return Err(()); // Unbalanced
        }
        Ok(1 + left_height.max(right_height))
    } else {
        Ok(-1) // Base height for null
    }
}

fn is_balanced(root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
    check_height(root).is_ok()
}

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

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

    println!("Is tree balanced? {}", is_balanced(&root));
}

let left_height = check_height(&n_borrow.left)?;

recursively get left subtree height or detect imbalance

let right_height = check_height(&n_borrow.right)?;

recursively get right subtree height or detect imbalance

if (left_height - right_height).abs() > 1 { return Err(()); }

check height difference to detect imbalance

Ok(1 + left_height.max(right_height))

return height of current node as max child height plus one

check_height(root).is_ok()

final check: if no imbalance found, tree is balanced

Output

Is tree balanced? true

Complexity Analysis

Time: O(n) because we visit each node once to calculate heights and check balance

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

vs Alternative: Naive approach recalculates heights repeatedly causing O(n^2) time; this approach combines height calculation and balance check in one pass for O(n)

Edge Cases

Empty tree (root is None)

Returns true since empty tree is balanced

DSA Rust

if let Some(n) = node { ... } else { Ok(-1) }

Single node tree

Returns true as single node is balanced

DSA Rust

if let Some(n) = node { ... } else { Ok(-1) }

Unbalanced tree with one side deeper by more than 1

Returns false due to height difference > 1 detected

DSA Rust

if (left_height - right_height).abs() > 1 { return Err(()); }

When to Use This Pattern

When a problem asks if a binary tree is balanced, use a bottom-up height check with early imbalance detection to avoid repeated height calculations.

Common Mistakes

Mistake: Calculating height separately for each node causing repeated work and O(n^2) time
Fix: Combine height calculation and balance check in one recursive function returning error on imbalance

Mistake: Using 0 as base height for null nodes causing off-by-one errors
Fix: Use -1 as base height for null nodes so leaf nodes have height 0

Summary

Checks if a binary tree is balanced by ensuring height difference of subtrees is at most one at every node.

Use when you need to verify tree balance efficiently without repeated height calculations.

The key insight is to return subtree heights and detect imbalance in one recursive pass.

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