Balanced Binary Tree

1. Problem & Core Objective

Return true if the tree is height-balanced — that is, if for every node the heights of its two subtrees differ by at most 1.

      3                        1
     / \                      / \
    9  20        true        2   2       false
       / \                  / \
      15  7                3   3
                          / \
                         4   4

Constraints: 0 <= nodes <= 5000 · -10^4 <= Node.val <= 10^4

What's actually being tested: the same O(n²) → O(n) collapse as question 3, solved a slightly different way — here a sentinel return value carries two facts at once. Also whether you notice the condition applies at every node, not just the root.

2. First-Principles Thought Process

Read the definition carefully

"Height-balanced" means the |left − right| <= 1 condition holds at every node. Checking only the root is wrong: a tree can have balanced top-level subtrees while a node three levels down is wildly lopsided.

The naive structure

isBalanced(node) = |height(left) − height(right)| <= 1
                   AND isBalanced(left)
                   AND isBalanced(right)

Correct, and O(n²) — for exactly the reason as question 3. height is called at every node and re-walks that node's whole subtree.

The fix: one value, two meanings

The redundancy is the same, so the fix is the same in spirit: compute heights once, bottom-up, and detect the imbalance on the way.

But unlike question 3, there's nothing to accumulate — I just need to propagate a failure. So instead of recording into a field, I can overload the return value:

Return the node's height — or −1 if the subtree is already known to be unbalanced.

This works because heights are never negative, so −1 is an unused value in the return domain. It's free to carry a second meaning.

Why that's the same idea as question 3

Both problems are "a naive recursion recomputes heights". Question 3 solves it by recording into a field; this one by encoding a flag into the return value. Which technique fits depends on whether you're accumulating a maximum or propagating a failure.

The short-circuit

Once any subtree returns −1, every ancestor returns −1 immediately without examining anything further. So a failure found deep in the tree stops the work above it.

3. Solution Paths

Approach 1 — Check the balance and the height separately (brute force)

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

private int height(TreeNode n) {
    if (n == null) return 0;
    return 1 + Math.max(height(n.left), height(n.right));
}

• Time O(n²) worst case, O(n log n) balanced · Space O(h)

Counter-questions on this approach

⭐ "Why is this O(n²) when both functions are linear?"

height is linear in the subtree it's called on, but isBalanced calls it at every node. On a degenerate chain the root's height call walks n nodes, the next walks n−1, and so on — O(n²).

Note the irony: it's worst on the unbalanced trees, which is where you'd most want a quick answer. On a genuinely balanced tree it's O(n log n).

⭐ "What information is being thrown away?"

Every height below the current node. height(root.left) computes the height of every node in that subtree and returns one number, discarding the rest — then the recursive isBalanced(root.left) recomputes exactly those.

The heights I need are already being produced. I just need to keep them on the way back up.

"Does the && short-circuit help?"

A little — an imbalance in the left subtree skips the right. But it doesn't change the asymptotics, because the expensive height calls happen before the short-circuit on the line above.

"Is O(n log n) on balanced input acceptable at n = 5000?"

It would pass. But the worst case is O(n²) = 2.5 × 10^7, which is also survivable — so the real argument isn't the runtime, it's that the single-pass version is shorter and shows the pattern.

Approach 2 — One traversal with a sentinel (optimal)

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

private int height(TreeNode n) {
    if (n == null) return 0;

    int L = height(n.left);
    if (L == -1) return -1;                       // already failed below — stop

    int R = height(n.right);
    if (R == -1) return -1;

    if (Math.abs(L - R) > 1) return -1;           // fails here
    return 1 + Math.max(L, R);                    // genuine height
}

Trace — the unbalanced example [1,2,2,3,3,null,null,4,4]:

| Node | L | R | |L−R| | Returns | |------|-----|-----|---------|---------| | 4, 4 (leaves) | 0 | 0 | 0 | 1 | | 3 (left, has two 4s) | 1 | 1 | 0 | 2 | | 3 (right leaf) | 0 | 0 | 0 | 1 | | 2 (left) | 2 | 1 | 1 | 3 | | 2 (right leaf) | 0 | 0 | 0 | 1 | | 1 (root) | 3 | 1 | 2 | −1 ✗ |

Returns -1, so isBalanced is false ✓

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why is −1 a safe sentinel? What if a height could be negative?"

Heights are counts of levels, so they're always >= 0 — an empty tree is 0 and every node adds one. −1 is therefore outside the natural range of the return value and is free to carry a second meaning.

If the return domain could include −1, this trick breaks and I'd need a different encoding: return a record (height, balanced), or throw and catch, or use Integer and return null. The sentinel works here because I checked the domain, not by convention.

⭐ "Why check L == -1 before computing R?"

Short-circuiting. Once any subtree is known unbalanced, the whole tree is unbalanced, and computing the right subtree's height is wasted work. On a tree that fails early on the left, this can skip nearly everything.

It also mirrors how && behaves in the naive version, but here it's explicit because the return value isn't a boolean.

"The function is named height but sometimes returns −1. Isn't that misleading?"

Fair criticism — it's the honest cost of the trick. In production I'd name it heightOrFailure and document the contract, or return a small record so the two outcomes are visible in the type. The compactness is worth it in an interview; the ambiguity isn't worth it in a codebase.

"How does this compare to question 3's mutable field?"

Same problem — an O(n²) recursion recomputing heights — with two different fixes. Question 3 accumulates a maximum, which needs somewhere to put it, so a field or an accumulator. This one propagates a failure, which can ride along in the return value. Choose by whether you're collecting or short-circuiting.

"What's the stack depth at n = 5000?"

Up to 5000 frames on a degenerate tree — but note that a degenerate tree fails the balance check almost immediately, so the short-circuit returns before descending far. The deep case is a balanced tree, where the height is only log 5000 ≈ 13. The two risks cancel out here, which is a pleasant accident worth noticing rather than assuming.

Comparison

4. Why the Optimal Wins

The naive version recomputes every height once per ancestor. The single pass computes each height exactly once and checks the balance at the same moment the two heights are in hand — the only moment when checking is free.

The elegance is the sentinel. One int return carries both "here is the height" and "this subtree already failed", which works only because heights can't be negative. Verifying that the sentinel is outside the real domain is the step people skip — and it's exactly where the technique silently breaks when reused elsewhere.

The framing worth keeping:

If a naive recursion calls a helper at every node, the helper is recomputing what the traversal already knows. Fold it into one pass — accumulating into a field if you need a maximum, or encoding a sentinel if you only need to fail.

5. Java Prerequisites

The sentinel pattern

if (childResult == FAILED) return FAILED;   // propagate without further work

Pick a sentinel provably outside the valid range — −1 for heights and counts, Integer.MIN_VALUE for sums that could be negative, or null with a boxed type when no value is safe.

Math.abs — note Math.abs(Integer.MIN_VALUE) is negative, an overflow quirk. Irrelevant here, but worth knowing.

Manual short-circuiting. With a boolean return, && does it for you. With an encoded return you must write the early exit yourself.

Height convention — height(null) = 0, so a leaf is 1. Matches question 2; a different convention shifts every comparison.

6. Interview Communication Guide

Clarifying questions: Does the balance condition apply at every node or only the root (every node — confirm, it's the trap)? Is "height" the node count or the edge count (node count here; it only affects the base case)? Can the tree be empty (yes, trivially balanced)?

The pitch

"The condition is that at every node, the two subtree heights differ by at most one — not just at the root. A tree can look balanced at the top and be lopsided three levels down.

The naive version checks that condition at each node by calling a height helper. That's O(n²), because height re-walks the whole subtree at every node — and it's worst on the unbalanced trees, which are exactly the ones you'd want to reject fast.

But the heights are already being computed during the traversal; they're just discarded. So I fold both jobs into one pass: recurse bottom-up computing heights, and check the difference at the moment both are in hand.

To report failure I overload the return value — return the height normally, or −1 if the subtree is already unbalanced. That's safe because heights are never negative, so −1 is outside the valid range and free to mean something else. I'd check that explicitly rather than assume it, since the trick breaks the moment the return domain includes the sentinel.

I also check L == -1 before computing R, so a failure on the left skips the right subtree entirely.

O(n) time, O(h) stack.

It's the same O(n²) collapse as the diameter problem, with a different fix: diameter accumulates a maximum so it needs a field, this one only needs to propagate a failure so it can ride in the return value."

Edge cases to volunteer:

Name the fifth one. The root's subtrees differ by 2 only because of an imbalance further down — it's the case that catches anyone who checks the root alone. And the last one matters too: <= 1 is allowed, so a strict < 1 rejects valid trees.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the first unbalanced node, not just a boolean."

Replace the −1 sentinel with a field holding the offending node, set on the first failure and checked before recursing further. The traversal is unchanged; only the payload grows. This is the point where I'd stop overloading the int and return a record instead — two facts fit in a sentinel, three don't.

⭐ "Allow a difference of at most k instead of 1."

Change > 1 to > k. Nothing structural changes, which is a good sign the solution captured the idea rather than the constant. Note that k >= n makes every tree balanced, and k = 0 requires a perfect tree.

"Rebalance the tree if it isn't balanced."

A different problem entirely. The simplest approach is to extract the sorted values via an inorder traversal and rebuild by repeatedly taking the middle element — O(n) time, and it produces a perfectly balanced BST. Incremental rebalancing is what AVL and red-black rotations do, and it's much more involved.

"What if the tree could be 10^6 nodes deep?"

Recursion would overflow. Convert to an explicit postorder stack with a map from node to height. Same complexity, frames on the heap. Note again that a 10^6-deep tree fails the balance check almost immediately — the short-circuit makes this less dangerous than it sounds, though you can't rely on that in general.

"How does this relate to AVL trees?"

AVL is exactly this invariant, maintained continuously: every node stores its height, and insertions or deletions that break |L − R| <= 1 trigger rotations to restore it. This problem is the check; AVL is the check plus the repair. That's why AVL nodes carry a height field — precomputing is what makes the check O(1) instead of O(n).

"Check whether the tree is complete rather than balanced."

Different property — a complete tree has every level full except possibly the last, filled left to right. BFS and verify that no non-null node appears after the first null. O(n) time, O(w) space, and it's what makes array-backed binary heaps possible.