Balanced Binary Tree
Last Updated: April 1, 2026
Understanding the Problem
We need to check whether a binary tree is "height-balanced." That means for every single node in the tree, the heights of its left and right subtrees differ by at most 1. Not just the root. Every node.
This is a subtle but important detail. A tree could have left and right subtrees of the root with heights 3 and 3, which looks balanced at the top level. But if some node buried deep in the left subtree has children with heights 0 and 2, the tree is unbalanced. So we need a way to verify the balance condition at every node, not just the root.
The key observation is that this is naturally 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
The most natural approach follows directly from the definition. A tree is balanced if, at the current node, the left and right subtree heights differ by at most 1, AND both subtrees are themselves balanced.
So we write a height() helper that computes the height of any subtree, then at each node we call height() on the left child and right child, compare them, and recurse deeper. It's straightforward and easy to reason about.
The catch? We're computing heights from scratch at every node. The root calls height() on its children. Then when we recurse into the left child, that node calls height() on its children again, recomputing heights that were already computed. But for an Easy problem, this works just fine.
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(n). The recursion stack can go as deep as the height of the tree. For a balanced tree that's O(log n), but for a skewed tree it's O(n).
At each node, height() traverses the entire subtree, and then the recursive calls recompute heights on overlapping subtrees. What if we computed 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, we combine both operations into a single recursive function. The idea is elegant: do a post-order DFS where each call returns the height of that subtree. But if at any point we detect an imbalance, we return a special sentinel value (-1) instead of a real height.
Think of it like this. In the top-down approach, we're asking each node "are you balanced?" and to answer, each node has to ask its entire subtree "how tall are you?" That's two separate questions requiring two separate traversals. In the bottom-up approach, we ask a single combined question: "how tall are you, or are you broken?" Each node gets the answer from its children, checks the balance condition, and passes the answer up. One traversal does everything.
The bottom-up approach works because it computes each node's height exactly once during a post-order traversal. By the time we process a node, we already have the definitive heights of both children. We check the balance condition right there and propagate either the valid height or the -1 sentinel upward.
The -1 sentinel acts as an "early termination" signal. Once any subtree is found to be unbalanced, that -1 bubbles up through every ancestor without doing any further meaningful computation. In the worst case (a balanced tree), we visit every node once. In the best case (imbalance detected early near the leaves), we short-circuit and skip large portions of the tree.
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).