Check if Binary Tree is Balanced in DSA Rust - Execution Trace

Concept Flow - Check if Binary Tree is Balanced

Start at root node

↓

Check left subtree height

↓

Check right subtree height

↓

Compare heights difference <= 1?

Yes No↓

Check left balanced?

↓

Check right balanced?

↓

Return true if both balanced

Start from root, recursively check left and right subtree heights and balance, return false if difference > 1, else true if both subtrees balanced.

Execution Sample

DSA Rust

fn is_balanced(root: &Option<Box<TreeNode>>) -> bool {
    fn height(node: &Option<Box<TreeNode>>) -> i32 {
        if let Some(n) = node {
            let left = height(&n.left);
            let right = height(&n.right);
            if left == -1 || right == -1 || (left - right).abs() > 1 {
                return -1;
            }
            left.max(right) + 1
        } else {
            0
        }
    }
    height(root) != -1
}

This code checks if a binary tree is balanced by recursively computing subtree heights and returning -1 if imbalance is found.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Balance Check	Return Value	Tree State
1	Start at root	Node 1	-	-	-	-	Root node present
2	Check left subtree height	Node 2	-	-	-	-	Traverse left subtree
3	Check left subtree height	Node 4	-	-	-	-	Traverse left subtree
4	Check left subtree height	None	-	-	-	0	Leaf reached, height 0
5	Check right subtree height	None	-	-	-	0	Leaf reached, height 0
6	Balance check at Node 4	Node 4	0	0	abs(0-0)=0 <=1	1	Balanced subtree height 1
7	Check right subtree height	Node 5	-	-	-	-	Traverse right subtree
8	Check left subtree height	None	-	-	-	0	Leaf reached, height 0
9	Check right subtree height	None	-	-	-	0	Leaf reached, height 0
10	Balance check at Node 5	Node 5	0	0	abs(0-0)=0 <=1	1	Balanced subtree height 1
11	Balance check at Node 2	Node 2	1	1	abs(1-1)=0 <=1	2	Balanced subtree height 2
12	Check right subtree height	Node 3	-	-	-	-	Traverse right subtree
13	Check left subtree height	None	-	-	-	0	Leaf reached, height 0
14	Check right subtree height	Node 6	-	-	-	-	Traverse right subtree
15	Check left subtree height	None	-	-	-	0	Leaf reached, height 0
16	Check right subtree height	None	-	-	-	0	Leaf reached, height 0
17	Balance check at Node 6	Node 6	0	0	abs(0-0)=0 <=1	1	Balanced subtree height 1
18	Balance check at Node 3	Node 3	0	1	abs(0-1)=1 <=1	2	Balanced subtree height 2
19	Balance check at root Node 1	Node 1	2	2	abs(2-2)=0 <=1	3	Balanced subtree height 3
20	Final result	-	-	-	-	true	Tree is balanced

💡 Traversal ends after checking all nodes; no imbalance found, so tree is balanced.

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 17	After Step 18	After Step 19	Final
Node Visited	-	Node 4	Node 5	Node 2	Node 6	Node 3	Node 1	-
Left Height	-	0	0	1	0	0	2	-
Right Height	-	0	0	1	0	1	2	-
Return Value	-	1	1	2	1	2	3	true

Key Moments - 3 Insights

Why do we return -1 when imbalance is detected?

Returning -1 signals imbalance to all higher recursive calls, so they can stop further checks early (see steps 6, 11, 18).

Why do we check if left or right height is -1 before comparing heights?

If either subtree is already unbalanced (-1), we propagate -1 immediately without further height checks (see steps 6 and 11).

Why is the height of an empty node 0?

An empty node means no subtree, so height is 0, which is the base case for recursion (see steps 4, 5, 8, 9, 13, 15, 16).

Visual Quiz - 3 Questions

Look at the execution_table, what is the height returned at step 11 for Node 2?

A 1

B -1

C 2

D 3

💡 Hint

Check the 'Return Value' column at step 11 in execution_table.

At which step does the algorithm confirm the tree is balanced?

A Step 20

B Step 19

C Step 18

D Step 11

💡 Hint

Look for the final result row in execution_table where 'Return Value' is true.

If the left subtree of Node 3 was taller by 2 levels, what would happen in the execution_table?

A Algorithm would continue checking right subtree

B Balance check at Node 3 would return -1

C Balance check at Node 3 would return height 2

D Final result would be true

💡 Hint

Recall the balance condition abs(left - right) > 1 returns -1 (imbalance).

Concept Snapshot

Check if Binary Tree is Balanced:
- Recursively compute left and right subtree heights
- If height difference > 1, return -1 (unbalanced)
- If any subtree returns -1, propagate -1 upwards
- If root returns != -1, tree is balanced
- Height of empty node = 0
- Time complexity: O(n) due to single pass recursion

Full Transcript

This visualization shows how to check if a binary tree is balanced by recursively calculating subtree heights. Starting at the root, the algorithm visits each node, computes the height of left and right subtrees, and checks if their height difference is more than 1. If imbalance is found, it returns -1 immediately to stop further checks. The height of an empty node is 0, which is the base case. The execution table traces each step, node visited, heights computed, and balance checks. The variable tracker shows how heights and return values change at key steps. Key moments clarify why -1 is used to signal imbalance and why empty nodes have height 0. The quiz tests understanding of height values, final result, and imbalance detection. This method efficiently checks balance in O(n) time by avoiding repeated height calculations.

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