You’re in a coding interview. The interviewer says: “Given a binary tree, determine if it’s height-balanced.” You know what balanced means: for every node, the height difference between left and right subtrees is at most 1. The naive approach computes height at every node, which is O(n²). The optimal approach computes height bottom-up in a single DFS and uses -1 as a sentinel to propagate “unbalanced” immediately. This is LeetCode #110, and the gap between the naive and optimal solutions is the entire interview signal.

This walkthrough covers the O(n²) trap, the sentinel technique, and how to present the improvement to your interviewer.

---

The Problem

Given a binary tree, determine if it is height-balanced. A binary tree is height-balanced if, for every node, the absolute difference between the heights of the left and right subtrees is at most 1. (LeetCode #110)

Example 1

Input:

    3
   / \
  9  20
    /  \
   15   7

Output: true

Example 2

Input:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Output: false

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Top-down vs. bottom-up	Do you identify the O(n²) trap and fix it?
Sentinel value technique	Do you use -1 (or None) to propagate “unbalanced” upward?
DFS with dual return	Can you return height AND balance status in one pass?
Code elegance	Can you express this in roughly 10 lines?

---

Step 1: Clarifying Questions

1. What does “balanced” mean exactly? Confirm: for every node, not just the root, the height difference must be ≤ 1.

2. Is an empty tree balanced? Yes, vacuously balanced.

3. Single-node tree? Yes, balanced with height 1.

---

Step 2: A First (Non-Optimal) Idea

For each node, compute the height of left and right subtrees, check if the difference ≤ 1, then recurse into both subtrees. The problem: height() is called redundantly. O(n) work at each of O(n) nodes = O(n²).

def isBalanced_naive(root) -> bool:
    if not root:
        return True
    left_h = height(root.left)
    right_h = height(root.right)
    if abs(left_h - right_h) > 1:
        return False
    return isBalanced_naive(root.left) and isBalanced_naive(root.right)

Approach	Time	Space
Naive (top-down)	O(n²)	O(h)

---

Step 3: The Key Insight

Compute height bottom-up, and use a sentinel value (-1) to propagate the “unbalanced” signal upward. If a subtree is unbalanced, return -1 immediately and short-circuit the entire check. This gives O(n) time, since each node is visited exactly once.

---

Step 4: Optimal Strategy

1. Write a helper check(node) that returns the height if balanced, or -1 if unbalanced.
2. Base case: check(None) returns 0.
3. Compute left = check(node.left) and right = check(node.right).
4. If either is -1, OR abs(left - right) > 1: return -1.
5. Otherwise return 1 + max(left, right).
6. isBalanced(root) returns check(root) != -1.

---

Python Implementation

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0

            left = check(node.left)
            if left == -1:
                return -1  # Short-circuit: left subtree is unbalanced

            right = check(node.right)
            if right == -1:
                return -1  # Short-circuit: right subtree is unbalanced

            if abs(left - right) > 1:
                return -1  # This node is not balanced

            return 1 + max(left, right)  # Return height to parent

        return check(root) != -1

---

Time and Space Complexity

Aspect	Complexity
Time	O(n), each node visited once
Space	O(h), call stack depth

---

Common Interview Mistakes

• Writing the O(n²) solution without noticing. Calling a separate height() function inside a recursive isBalanced() is the trap.

• Checking only the root. Balance must hold at every node, not just the root.

• Using -1 without explaining why. State clearly: -1 is a sentinel that means “unbalanced; propagate immediately.”

• Forgetting to short-circuit on -1. If you compute both left and right before checking for -1, you’ve lost the early-exit benefit.

---

What a Strong Candidate Sounds Like

“The naive approach calls height at every node, which is O(n²). Instead, I compute height bottom-up in a single DFS and return -1 as a sentinel if any subtree is unbalanced. Since -1 propagates immediately, we short-circuit on the first imbalance and never recompute anything. Single pass, O(n).”

---

Example Interview Dialogue

Interviewer: Walk me through an unbalanced example.

Candidate: Take the second example: the root’s left subtree has depth 4, right subtree has depth 2. When my helper reaches node 2 on the left side, it computes left = 3 and right = 1, so abs(3-1) = 2 > 1. It returns -1. That -1 propagates up to node 1, which immediately returns -1 without checking the right subtree. isBalanced sees -1 and returns false.

---

Related Problems to Practice

• Maximum Depth of Binary Tree (LeetCode #104). The height computation used here.
• Diameter of Binary Tree (LeetCode #543). Same “track extra info alongside height” pattern.
• Binary Tree Maximum Path Sum (LeetCode #124). Harder version of the same paradigm.

---

Practice This in a Mock Interview

Balanced Binary Tree is a problem where the gap between “correct” and “optimal” can cost you a hire/no-hire decision. Recognizing the O(n²) trap and fixing it with the sentinel approach is the minimal bar for a strong answer.

Start a mock interview for Balanced Binary Tree on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code