Check if Binary Tree is Balanced in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of balance check on a simple balanced tree

What is the output of the following Rust code that checks if a binary tree is balanced?

DSA Rust

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

#[derive(Debug)]
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 is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let left_height = height(&n.borrow().left);
                if left_height == -1 {
                    return -1;
                }
                let right_height = height(&n.borrow().right);
                if right_height == -1 {
                    return -1;
                }
                if (left_height - right_height).abs() > 1 {
                    return -1;
                }
                1 + left_height.max(right_height)
            }
        }
    }
    height(&root) != -1
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().right = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(4));
    println!("{}", is_balanced(Some(root)));
}

A false

B Runtime panic

C Compilation error

D true

💡 Hint

Think about the height difference between left and right subtrees at each node.

The tree is balanced because for every node, the height difference between left and right subtrees is at most 1.

The function returns true.

❓ Predict Output

intermediate

Output of balance check on an unbalanced tree

What is the output of the following Rust code that checks if a binary tree is balanced?

DSA Rust

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

#[derive(Debug)]
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 is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let left_height = height(&n.borrow().left);
                if left_height == -1 {
                    return -1;
                }
                let right_height = height(&n.borrow().right);
                if right_height == -1 {
                    return -1;
                }
                if (left_height - right_height).abs() > 1 {
                    return -1;
                }
                1 + left_height.max(right_height)
            }
        }
    }
    height(&root) != -1
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(4));
    println!("{}", is_balanced(Some(root)));
}

A false

B Runtime panic

C true

D Compilation error

💡 Hint

Check the height difference at the root node.

The tree is unbalanced because the left subtree is much deeper than the right (which is empty).

The function returns false.

🧠 Conceptual

advanced

Understanding the height function in balance check

In the balance check function, why does the height function return -1?

A To indicate the subtree is balanced

B To indicate the subtree is unbalanced

C To indicate the subtree is empty

D To indicate the subtree has equal height on both sides

💡 Hint

Think about what a special return value might mean in a recursive check.

The height function returns -1 as a special signal that the subtree is unbalanced.

🔧 Debug

advanced

Identify the bug causing incorrect balance result

Given this Rust code snippet for balance check, which option explains why it incorrectly returns true for an unbalanced tree?

DSA Rust

fn height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match node {
        None => 0,
        Some(n) => {
            let left_height = height(&n.borrow().left);
            let right_height = height(&n.borrow().right);
            if (left_height - right_height).abs() > 1 {
                return 0; // Bug here
            }
            1 + left_height.max(right_height)
        }
    }
}

A The function uses max instead of min for height calculation

B The function does not check for None nodes correctly

C Returning 0 instead of -1 does not signal unbalance, so function always returns true

D The function does not recurse on both left and right subtrees

💡 Hint

What special value is used to indicate unbalance?

Returning 0 instead of -1 fails to propagate the unbalanced signal, so the main function thinks the tree is balanced.

🚀 Application

expert

Number of nodes visited during balance check

For a complete binary tree with 7 nodes, how many nodes does the balance check function visit in the worst case?

A 7

B 6

C 14

D 3

💡 Hint

The function visits each node once to compute height.

The function visits every node once to compute heights and check balance.

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