Bird
Raised Fist0

Given this binary tree:

easy🧾 Trace Q3 of Q15
Tree: Depth-First Search - Balanced Binary Tree
Given this binary tree:
    5
   / \
  3   8
 / \
1   4
and the following recursive function to check balance:
def check(node):
    if not node:
        return 0
    left = check(node.left)
    if left == -1:
        return -1
    right = check(node.right)
    if right == -1:
        return -1
    if abs(left - right) > 1:
        return -1
    return max(left, right) + 1
What does check(root) return for this tree?
A3
B-1
C2
D0
Step-by-Step Solution
Solution:
  1. Step 1: Compute heights bottom-up

    Leaf nodes 1 and 4 return 1, node 3 returns max(1,1)+1=2, node 8 returns 1.
  2. Step 2: Check balance at each node

    All nodes have height difference ≤ 1, so no -1 returned.
  3. Step 3: Root node 5 returns max(2,1)+1=3

  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Balanced tree height is 3 [OK]
Quick Trick: Balanced tree returns height, not -1 [OK]
Common Mistakes:
MISTAKES
  • Confusing height with balance flag
  • Returning -1 prematurely
  • Miscomputing subtree heights
Trap Explanation:
PITFALL
  • Returning -1 only on imbalance, not on balanced nodes
Interviewer Note:
CONTEXT
  • Tests ability to trace recursive balanced tree check
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