Bird
Raised Fist0

Examine this code snippet for checking if a binary tree is balanced:

medium🐞 Bug Q7 of Q15
Tree: Depth-First Search - Balanced Binary Tree
Examine this code snippet for checking if a binary tree is balanced:
def is_balanced(root):
    def height(node):
        if node is None:
            return 0
        left_height = height(node.left)
        right_height = height(node.right)
        if abs(left_height - right_height) > 1:
            return -1
        return max(left_height, right_height) + 1
    return height(root) != -1
Which issue could cause incorrect results on trees with null nodes?
ANo early exit on detecting imbalance
BReturning -1 does not propagate imbalance correctly
CNot checking if left_height or right_height is -1 before comparing
DIncorrect base case returning 0 for null nodes
Step-by-Step Solution
Solution:
  1. Step 1: Identify problem

    The code does not check if left_height or right_height is -1 before comparing heights.
  2. Step 2: Consequence

    If a subtree is unbalanced (returns -1), the parent still compares -1 with a height, causing wrong results.
  3. Step 3: Fix

    Check if left_height == -1 or right_height == -1 and propagate -1 immediately.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Always propagate -1 early to avoid false positives [OK]
Quick Trick: Check for -1 before height difference check [OK]
Common Mistakes:
MISTAKES
  • Ignoring early imbalance propagation
  • Assuming height difference check handles -1 correctly
  • Misunderstanding base case returns
Trap Explanation:
PITFALL
  • Comparing -1 as height leads to incorrect balance detection
Interviewer Note:
CONTEXT
  • Tests ability to spot subtle bugs in recursive balance checks
Master "Balanced Binary Tree" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes