Balanced Binary Tree: why you need to stop recalculating height

Height-balanced means every node in the tree satisfies one condition: the height of its left subtree and the height of its right subtree differ by at most one. Not just the root. Every node. That global requirement is what makes the naive solution slow — checking balance at the root is easy, but confirming it everywhere forces you to visit every node, and each visit triggers its own height calculation if you are not careful.

The tree above is balanced. Node 9 has height 1, node 20 has height 2 — difference at the root is 1, which is allowed. Every subtree also passes: node 20's children both have height 1. Now add a left child to node 9 and add a left child to that child and you have the classic unbalanced case — depth piles up on one side while the other stays flat.

The problem

Given a binary tree, determine whether it is height-balanced — meaning every node in the tree has left and right subtrees whose heights differ by at most one. Full statement: LeetCode 110.

Constraints:
- The number of nodes in the tree is in the range [0, 5000].
- -104 <= Node.val <= 104

What the constraints force

The problem allows up to 5000 nodes and values in [-10^4, 10^4]. The value range is irrelevant — balance is purely structural. The node count is the interesting one.

n <= 5000 does not rule out O(n²). An O(n²) solution runs in at most 25 million operations, which is fast enough on any modern machine. So the constraints do not force you to find the optimal solution. What forces it is understanding why the naive approach is wasteful and whether you can do better — and you can, dramatically so, with a single pass.

The tree can be empty (n = 0), and an empty tree is balanced by definition. That case falls cleanly out of any correct implementation as long as you handle null nodes.

Approach 1: top-down height recalculation

The most direct reading of the problem definition: for every node, compute the height of its left and right subtrees, check the difference is at most 1, then recurse into both children.

class Solution:
    def isBalanced(self, root) -> bool:
        if not root:
            return True
 
        left_h = self.getHeight(root.left)
        right_h = self.getHeight(root.right)
 
        if abs(left_h - right_h) > 1:
            return False
 
        return self.isBalanced(root.left) and self.isBalanced(root.right)
 
    def getHeight(self, node) -> int:
        if not node:
            return 0
        return 1 + max(self.getHeight(node.left), self.getHeight(node.right))

public class Solution {
    public bool IsBalanced(TreeNode root) {
        if (root == null) return true;
 
        int leftH = GetHeight(root.left);
        int rightH = GetHeight(root.right);
 
        if (Math.Abs(leftH - rightH) > 1) return false;
 
        return IsBalanced(root.left) && IsBalanced(root.right);
    }
 
    private int GetHeight(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.Max(GetHeight(node.left), GetHeight(node.right));
    }
}

This works. The logic is clear and the code maps directly to the definition. The problem is the redundant work. When IsBalanced is called on the root, GetHeight walks the entire tree to compute the root's subtree heights. Then IsBalanced recurses into the left child, and GetHeight walks that subtree again — including all the nodes in that subtree's left and right children. Every node in the tree contributes to multiple height calculations. In the worst case, a balanced tree of height h causes each node at depth d to have its subtree traversed h - d times. That is O(n log n) for a balanced tree and O(n²) for a skewed chain.

Time and space complexity

Time: O(n²) worst case. For a fully left-skewed tree of n nodes (a chain), the root triggers a height calculation over all n nodes. The root's left child triggers one over n - 1 nodes. And so on. Total: n + (n-1) + ... + 1 = n(n+1)/2.

Space: O(n) for the call stack. The recursion depth equals the tree height, which is O(n) for a skewed chain.

Approach 2: bottom-up — height and balance in one pass

The insight is that getHeight and isBalanced are doing overlapping work on the same nodes. You do not need to separate them. Instead, write a single function that returns the height of a subtree if it is balanced, or a sentinel value (-1) if it is not. Process children first, then the parent — post-order traversal.

class Solution:
    def isBalanced(self, root) -> bool:
        def check(node) -> int:
            if not node:
                return 0
 
            left_h = check(node.left)
            if left_h == -1:
                return -1
 
            right_h = check(node.right)
            if right_h == -1:
                return -1
 
            if abs(left_h - right_h) > 1:
                return -1
 
            return 1 + max(left_h, right_h)
 
        return check(root) != -1

public class Solution {
    public bool IsBalanced(TreeNode root) {
        return Check(root) != -1;
    }
 
    private int Check(TreeNode node) {
        if (node == null) return 0;
 
        int leftH = Check(node.left);
        if (leftH == -1) return -1;
 
        int rightH = Check(node.right);
        if (rightH == -1) return -1;
 
        if (Math.Abs(leftH - rightH) > 1) return -1;
 
        return 1 + Math.Max(leftH, rightH);
    }
}

The -1 sentinel is the key design decision. A real height is always non-negative, so -1 is unambiguous as "this subtree is unbalanced, stop propagating." Once check(node.left) returns -1, you short-circuit immediately — you do not even call check(node.right). The imbalance signal propagates up the call stack and the whole function returns before examining unneeded branches.

Hand trace through Example 1: [3, 9, 20, null, null, 15, 7]

Processing order is post-order — leaves first:

• Step 1: check(9). Both children null, return 0 each. |0 - 0| = 0 <= 1. Return 1 + max(0, 0) = 1.
• Step 2: check(15). Both children null. Return 1.
• Step 3: check(7). Both children null. Return 1.
• Step 4: check(20). Left returns 1, right returns 1. |1 - 1| = 0 <= 1. Return 1 + max(1, 1) = 2.
• Step 5: check(3). Left returns 1, right returns 2. |1 - 2| = 1 <= 1. Return 1 + max(1, 2) = 3.

Final result: check(root) = 3, which is not -1, so isBalanced returns true.

Now trace the unbalanced case [1, 2, 2, 3, 3, null, null, 4, 4]:

• check(4) and check(4) (leaves): both return 1.
• check(3) (left child of the left-2): left = 1, right = 1. Returns 2.
• check(3) (right child of the left-2): both children null. Returns 1.
• check(2) (left child of root): left = 2, right = 1. |2 - 1| = 1 <= 1. Returns 3.
• check(2) (right child of root): both children null. Returns 1.
• check(1) (root): left = 3, right = 1. |3 - 1| = 2 > 1. Returns -1.

check(root) == -1, so isBalanced returns false.

Time and space complexity

Time: O(n). Every node is visited exactly once. No redundant traversals.

Space: O(h) where h is the tree height. Best case O(log n) for a balanced tree, worst case O(n) for a skewed chain. The call stack depth equals the tree height.

Edge cases

Empty tree (root = null). Both approaches return true immediately — either from the null check in isBalanced, or from check returning 0 (which is not -1). An empty tree satisfies the balance definition vacuously.

Single node. The node's left and right children are both null, so height difference is 0. Returns true. No subtlety here.

Perfectly right-skewed chain ([1, null, 2, null, 3, ...]). For the top-down approach this is the worst case: O(n²) because getHeight walks the entire remaining chain at every level. For bottom-up, each node is still visited once — O(n) regardless of shape. The skewed chain is also the worst case for space in both: O(n) stack depth.

Subtree that is almost balanced. The definition requires every node to satisfy the condition, not just the root. A tree like [1, 2, 3, 4, 5, null, null, 6] might look balanced at the root but have an imbalanced subtree deeper down. The bottom-up approach catches this naturally — the imbalance propagates upward as a -1 without requiring any additional logic. The top-down approach also catches it but recomputes heights unnecessarily.

Node.val at boundaries (-10^4 and 10^4). Values do not affect balance. The algorithm never reads node.val at all — you can ignore this boundary entirely.

Comparison

The space for bottom-up is O(h) not O(n) — for a balanced tree that is O(log n), which is a real improvement even if the worst case is the same O(n) on a skewed chain.

Which one I would ship

Bottom-up, immediately, for any production use. The top-down version has the appeal of being an almost literal transcription of the problem statement — and in an interview, writing it first to confirm you understand the definition is a legitimate strategy. But stop there, explain the redundancy, and then write the bottom-up version.

The pattern the bottom-up approach embodies is worth naming: use a sentinel return value to carry a failure signal up the recursion without a global variable or a separate pass. You see this in Diameter of Binary Tree (543), where you carry the diameter as a side-channel while returning height from the recursive function. You see it in Maximum Depth (104) in simpler form. The idea is that post-order traversal gives you a natural accumulation point — by the time you process a node, you have complete information from both subtrees already.

The -1 sentinel is one choice. Another is returning a tuple (is_balanced, height). The sentinel is more compact; the tuple is more explicit. Either is correct; pick the one your team can read without the comment.

Where this sits in the trees series

This is problem eight in the series. It follows Validate BST (98) and Subtree of Another Tree (572). The three traversal primitives — DFS recursion, BFS with a queue, post-order accumulation — were established earlier. Balanced Binary Tree is the first problem in the series that makes the inefficiency of naive top-down traversal concrete. The bottom-up pattern introduced here reappears constantly.

Diameter of Binary Tree (543) is the most direct follow-on. You use the same post-order pass but instead of carrying a failure sentinel, you carry both the height and the diameter as you return from each recursive call. The structural trick is identical.

Maximum Depth of Binary Tree (104) is simpler but uses the same bottom-up height calculation. If 104 felt trivial, 110 shows exactly why height calculations matter beyond the obvious case.

Path Sum II (113) goes in a different direction: instead of accumulating results from children on the way back up, you pass state downward and record complete paths at leaves. The contrast clarifies when to push information down vs pull it up.

Binary Tree Maximum Path Sum (124) is the hard version of this pattern. You carry both a "single path" value (the useful return) and a "complete path through this node" value (a side-channel update to a global max). The sentinel trick from 110 and the side-channel trick from 543 both appear there, under harder constraints.