Balanced Binary Tree
Understanding the Problem
We need to check whether a binary tree is "height-balanced": for every node in the tree, the heights of its left and right subtrees differ by at most 1. The condition applies to every node, not only the root.
A tree can look balanced from the top while hiding a violation deeper down. If the root's subtrees both have height 3, the root passes the check, but a node inside the left subtree whose children have heights 0 and 2 still makes the whole tree unbalanced. The check has to run at every node.
The definition is recursive. A tree is balanced if and only if: (1) the left subtree is balanced, (2) the right subtree is balanced, and (3) the height difference between the left and right subtrees at the current node is at most 1. All three conditions must hold.
Key Constraints:
Number of nodes in [0, 5000]→ With n up to 5,000, even O(n^2) gives us 25 million operations, which is fine. But we can do better with O(n).-10^4 <= Node.val <= 10^4→ Node values don't affect our algorithm at all. We only care about the tree's structure, not the values stored in it.0 nodesis valid → We need to handle the empty tree case. An empty tree is balanced.
Approach 1: Top-Down Recursion (Brute Force)
Intuition
Apply the definition node by node. At the current node, compute the heights of the left and right subtrees and compare them. If they differ by more than 1, return false. Otherwise run the same check on both children, since balance must hold at every node, not only here.
A height() helper does the measuring: an empty subtree has height 0, and any other node has height 1 plus the larger of its children's heights.
The cost is repeated work. The root calls height() on its children, which visits every node below them. Recursing into the left child then recomputes those same heights one level down. With n up to 5,000, this redundancy still passes.
Algorithm
- If the current node is null, return true (an empty tree is balanced).
- Compute the height of the left subtree.
- Compute the height of the right subtree.
- If the absolute difference between the two heights is greater than 1, return false.
- Recursively check if the left subtree is balanced.
- Recursively check if the right subtree is balanced.
- Return true only if all three conditions are satisfied.
Example Walkthrough
Code
- Time Complexity: O(n log n) for balanced trees, O(n^2) for skewed trees. At each node, we call
height()which visits all nodes in that subtree. For a balanced tree, this gives O(n) work per level across O(log n) levels. For a skewed tree, the height call at depth d touches n - d nodes, summing to O(n^2). - Space Complexity: O(h), where h is the height of the tree, for the recursion stack (O(n) worst case for a skewed tree). For a balanced tree, h = O(log n).
At each node, height() traverses the entire subtree below it, and the recursive balance checks then traverse those same subtrees again. The next approach computes each node's height exactly once during a single bottom-up traversal.
Approach 2: Bottom-Up DFS (Optimal)
Intuition
Instead of computing heights separately and then checking balance, combine both operations into a single recursive function: a post-order DFS where each call returns the height of its subtree, or a sentinel value of -1 if that subtree is unbalanced. Heights are never negative, so -1 cannot be confused with a real height.
The top-down approach asks two separate questions at each node, "is this node balanced?" and "how tall is each subtree?", and answering the second requires its own traversal. The bottom-up version merges them into one. Because the traversal is post-order, both children's heights are final by the time a node is processed, so the balance check happens on the spot and the result (height or -1) passes upward. Once any call returns -1, every ancestor propagates it without computing anything else, so the traversal effectively stops at the first violation.
Algorithm
- Define a helper function
checkHeight(node)that returns the height of the subtree if balanced, or -1 if unbalanced. - If the node is null, return 0 (base case: empty subtree has height 0).
- Recursively get the left subtree's height. If it's -1, immediately return -1 (left subtree is unbalanced, no need to check further).
- Recursively get the right subtree's height. If it's -1, immediately return -1.
- If the absolute difference between left and right heights exceeds 1, return -1 (current node violates balance).
- Otherwise, return 1 + max(leftHeight, rightHeight) as the valid height.
- In the main function, call
checkHeight(root)and return true if the result is not -1.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited exactly once during the post-order traversal. At each node, we do O(1) work (compare heights, compute max).
- Space Complexity: O(h), where h is the height of the tree. The space comes from the recursion stack. For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n).
Approach 3: Iterative Post-Order with an Explicit Stack
Intuition
Both solutions so far rely on recursion, and recursion depth equals tree height. A 5,000-node tree arranged in a single chain produces 5,000 nested calls, which exceeds Python's default recursion limit of 1,000 and can overflow fixed-size call stacks in other runtimes. The same bottom-up computation runs on an explicit stack with no depth limit.
The algorithm does not change: child heights must be known before each parent is checked. Only the bookkeeping changes. A stack holds nodes waiting to be processed, and a hash map stores the height of every finished subtree.
When a node is popped, there are two cases. If either child's height is missing from the map, push the node back, then push the unfinished children; by the time the node is popped again, both child heights exist. If both child heights are available, run the balance check: a difference greater than 1 ends the run with false, and otherwise the node's own height, 1 plus the larger child height, goes into the map. A null child counts as height 0. If the stack empties without a violation, the tree is balanced.
The trade-off is memory. Recursion stores heights implicitly in stack frames and uses O(h) space; the map stores a height for every node and uses O(n). The gain is independence from the call-stack limit, not a better bound.
Algorithm
- If the root is null, return true. Otherwise create an empty
heightsmap and push the root onto a stack. - Pop a node. A child counts as done if it is null or already has an entry in
heights. - If either child is not done, push the node back, push each unfinished child, and continue with the next iteration.
- If both children are done, read their heights from the map, using 0 for a null child. If the difference exceeds 1, return false.
- Otherwise store 1 + max(leftHeight, rightHeight) as the node's height in the map.
- When the stack is empty, every node passed the check. Return true.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is pushed at most twice (once before its children are processed, once after), and the work per pop is a constant number of hash-map operations, O(1) on average.
- Space Complexity: O(n). The heights map holds one entry per node, and the stack can hold up to O(n) nodes. This is more memory than the recursive solution's O(h); the benefit is the depth limit, not the space.