Balanced Binary Tree
Problem Statement
Given the root of a binary tree, determine whether it is height-balanced. A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by no more than 1.
Input
The root pointer of a binary tree, or null for an empty tree.
Output
A boolean: true if every node is height-balanced, otherwise false.
Constraints
- •
0 <= number of nodes <= 5000 - •
-10^4 <= Node.val <= 10^4
Examples
Example 1
root = [3,9,20,null,null,15,7]
trueExample 2
root = [1,2,2,3,3,null,null,4,4]
falseExample 3
root = []
trueLearning Objectives
- Recognise balance checking as a bottom-up height aggregation problem.
- Use a sentinel value to combine height computation and unbalanced detection in one DFS.
- Short-circuit recursion as soon as any subtree is known to be unbalanced.
- Explain why recomputing heights at every node is avoidable.
Intuition
Pattern Recognition
The signal is a property that must hold at every node, and the property depends on subtree heights. A top-down solution can ask for the height of each subtree repeatedly, but that repeats work on the same descendants. The better pattern is bottom-up: let each child report its height once.
The twist is failure propagation. If a child subtree is already unbalanced, the parent does not need its exact height anymore. Return a sentinel such as -1 to mean unbalanced. That sentinel moves upward immediately, giving an O(n) solution instead of repeatedly recomputing heights.
Common mistakes
- ×Checking only whether the root is balanced and ignoring deeper nodes.
- ×Calling a separate height function for every node, which can revisit the same subtree many times.
- ×Returning a normal height after discovering an unbalanced child instead of propagating **-1**.
- ×Using **null** as unbalanced even though **null** should have height **0** and be balanced.
Algorithm Explanation
Key idea
Use one recursive function that returns either a real height or the sentinel -1. For a null node, return height 0. For a real node, ask the left subtree for its value first. If it returns -1, immediately return -1. Then do the same for the right subtree. If both sides are valid but their heights differ by more than 1, return -1. Otherwise return the actual height.
Recursion walkthrough
For the balanced tree [3,9,20,null,null,15,7], leaves 9, 15, and 7 each return height 1. Node 20 receives heights 1 and 1, so it returns 2. Root 3 receives left height 1 and right height 2, and the difference is 1, so the whole tree returns height 3 and the answer is true.
For a skewed subtree such as [1,2,2,3,null,null,null,4], leaf 4 returns 1, node 3 returns 2, and the left child 2 sees left height 2 and right height 0. That difference is 2, so it returns -1. When root 1 receives -1 from its left child, it can return -1 without needing the right subtree height.
Algorithm
- Define a helper that returns subtree height, or -1 if that subtree is unbalanced.
- Return 0 for a null node.
- Recursively compute the left height; if it is -1, return -1 immediately.
- Recursively compute the right height; if it is -1, return -1 immediately.
- If abs(leftHeight - rightHeight) > 1, return -1.
- Otherwise return 1 + max(leftHeight, rightHeight).
- The tree is balanced exactly when the helper result is not -1.
Solutions
Solution: Bottom-up height with sentinel
Use this in interviews because it avoids repeated height calculations and makes early failure propagation explicit.
Compute height bottom-up, but return -1 instead of a height as soon as a subtree is unbalanced. Parents treat -1 as a hard failure and propagate it without doing extra work.
Step-by-step
- Return 0 for null because an empty subtree is balanced with height 0.
- Recursively ask the left subtree for a height-or-sentinel value.
- If the left value is -1, return -1 immediately.
- Recursively ask the right subtree for a height-or-sentinel value.
- If the right value is -1 or the two heights differ by more than 1, return -1.
- Otherwise return the normal height 1 + max(leftHeight, rightHeight).
- Convert the root helper value into a boolean by checking whether it is not -1.
O(n)
O(h)
Each node is visited at most once, and the recursion stack is proportional to tree height.
Java implementation
Dry Run
Sample input
root = [1,2,2,3,null,null,null,4]. The left subtree becomes unbalanced before the root needs to inspect the right subtree.
| node | leftHeight | rightHeight | returned value | meaning |
|---|---|---|---|---|
| 4 | 0 | 0 | 1 | leaf is balanced |
| 3 | 1 | 0 | 2 | height difference is 1 |
| 2 | 2 | 0 | -1 | height difference is 2, so this subtree is unbalanced |
| 1 | -1 | skipped | -1 | left sentinel short-circuits the root |
The sentinel -1 means the exact height no longer matters. Once it reaches the root, the final answer is false.
Interview Tips
Emphasise that the helper has a dual meaning: non-negative values are real heights, and -1 means this subtree is already invalid. That lets you short-circuit while still doing a single postorder traversal. Interviewers often look for this because it avoids the common O(n log n) or O(n^2) repeated-height pattern.
Likely follow-ups
- How would you return the first node where the balance condition fails?
- How would the condition change for an AVL tree with stored heights?
- Can you solve the same check iteratively with an explicit stack?
- How would you maintain balance information while inserting into a tree?
Similar Problems
Key Takeaways
- Balance must be checked at every node, not just at the root.
- A sentinel lets one DFS compute heights and propagate failure together.
- Return **-1** immediately when a child subtree is unbalanced.
- The optimal solution visits each node once and uses O(h) recursion stack.