Check if Binary Tree is Balanced in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define a binary tree node struct with optional children.

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: [1],
            right: None,
        }
    }
}

Drag options to blanks, or click blank then click option'

ANone

BSome(Box::new(TreeNode::new(val)))

CSome(TreeNode::new(val))

DBox::new(TreeNode::new(val))

Attempts:

3 left

💡 Hint

Common Mistakes

Using Some(...) instead of None for children in new node.

Trying to assign a raw TreeNode instead of Boxed TreeNode.

When creating a new node, its children should start as None (no children).

2fill in blank

medium

Complete the function signature to check if a binary tree is balanced.

DSA Rust

fn is_balanced(root: &Option<Box<TreeNode>>) -> bool {
    [1]
}

Drag options to blanks, or click blank then click option'

Aroot.is_none() || (check_balance(root).0)

Broot.is_some()

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true unconditionally.

Checking only if root is_some without balance logic.

The tree is balanced if empty or if check_balance returns true in its first value.

3fill in blank

hard

Fix the error in the helper function that returns (bool, i32) for balance and height.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A>=

B<

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using == 1 instead of <= 1 causes imbalance detection errors.

Using > or >= reverses the logic.

The tree is balanced if the height difference is at most 1 (<= 1).

4fill in blank

hard

Fill both blanks to complete the recursive height calculation and balance check.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cval

Dnew

Attempts:

3 left

💡 Hint

Common Mistakes

Using val or new instead of left or right causes errors.

Swapping left and right changes logic but still compiles.

We recursively check the left and right children for balance and height.

5fill in blank

hard

Fill all three blanks to complete the main function calling the helper and returning the balance result.

DSA Rust

fn is_balanced(root: &Option<Box<TreeNode>>) -> bool {
    if root.[1]() {
        return true;
    }
    let (balanced, _) = check_balance(&root.[2]);
    balanced && check_balance(&root.[3]).0
}

Drag options to blanks, or click blank then click option'

Ais_none

Bleft

Cright

Dunwrap

Attempts:

3 left

💡 Hint

Common Mistakes

Using unwrap() instead of is_none() causes panic on empty tree.

Checking only one child subtree misses full balance check.

Check if root is None, then check balance of left and right subtrees.

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