Balanced Binary Tree Check, in depth: the definition, the O(n) post-order pass, iterative versions and the traps

What balanced means, precisely

A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by at most one. The definition is recursive and local: it constrains every node, not just the root. A root whose two subtrees have equal height can still sit on top of a badly lopsided subtree, and that tree is not balanced.

Height needs a convention. In this article the height of an empty tree is 0 and the height of a leaf is 1, so the height of a node is one plus the larger of its children's heights. Some texts use -1 for the empty tree and 0 for a leaf. Either works as long as you never mix them, because the balance test only compares differences. The convention matters for the sentinel trick below, which reserves -1 to mean "unbalanced" and therefore needs -1 to be an impossible height.

Two things are often confused with balance. A complete tree fills every level except possibly the last, left to right; every complete tree is balanced but not the reverse. A perfect tree has all leaves at the same depth. Balance is the weaker property, and it is the one that guarantees height grows logarithmically: a height-balanced tree with n nodes has height at most about 1.44 log2(n), the same bound as AVL trees, because AVL trees are exactly binary search trees that keep this invariant.

A worked example

In tree A, leaves 4, 5 and 3 have height 1. Node 2 sees heights 1 and 1, difference 0, so it has height 2. The root sees 2 on the left and 1 on the right, difference 1, which is allowed. Every node passes, so A is balanced.

In tree B, node 5 has height 1 and node 4 has height 2 with an empty right child, a difference of 1, which passes. Node 2 has a left height of 2 and a right height of 0, a difference of 2, which fails. Once one node fails the whole tree is unbalanced, and a well-written check stops there.

A useful variant to test yourself on: a root whose left subtree is a chain of three nodes and whose right subtree is also a chain of three nodes. The root compares 3 and 3 and is happy, but the second node on each side compares 2 and 0. A check that only inspects the root gets this wrong.

The top-down approach and its real cost

The direct translation of the definition computes heights at each node and recurses:

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def is_balanced_naive(node):
    if node is None:
        return True
    if abs(height(node.left) - height(node.right)) > 1:
        return False
    return is_balanced_naive(node.left) and is_balanced_naive(node.right)

It is correct, and on small inputs it is fine. The problem is that height walks a whole subtree, and the recursion calls it again for every descendant. A node at depth d has its subtree's heights recomputed once by each of its d ancestors' checks plus its own. The total work is the sum over all checked nodes of their subtree sizes, which equals the sum of all node depths, bounded by n times the tree height h.

That gives the honest complexity. On a balanced tree, h is O(log n), so the naive check costs O(n log n). On an unbalanced tree it usually fails near the top and stops early, and in general the cost is bounded by O(n times h), not a flat O(n squared). Measured on perfect trees, the number of height calls was 18,434 for 1,023 nodes, 425,986 for 16,383 nodes and 4,194,306 for 131,071 nodes: about 18, 26 and 32 calls per node, growing with log n exactly as the analysis says. Calling it "O(n squared)" as a blanket statement, which many write-ups do, overstates the cost on the inputs where the check matters most.

The linear pass: heights flow up, failure short-circuits

The fix is to compute each height once, in post-order, and to let a node report failure through the same return value. Because real heights are never negative, -1 is free to mean "some node below me is unbalanced".

UNBALANCED = -1

def check(node):
    """Return the height of node's subtree, or UNBALANCED."""
    if node is None:
        return 0
    lh = check(node.left)
    if lh == UNBALANCED:
        return UNBALANCED          # stop: do not even visit the right subtree
    rh = check(node.right)
    if rh == UNBALANCED:
        return UNBALANCED
    if abs(lh - rh) > 1:
        return UNBALANCED
    return 1 + max(lh, rh)

def is_balanced(root):
    return check(root) != UNBALANCED

Each node is visited at most once and does constant work, so the running time is O(n) and the extra space is the recursion depth, O(h). On tree B, check returns -1 at node 2, and the root returns -1 without visiting node 3. Running the code gives is_balanced(A) == True and is_balanced(B) == False.

The same function in Java, where a sentinel is the idiomatic choice because returning a pair allocates:

static final int UNBALANCED = -1;

static int check(TreeNode node) {
    if (node == null) return 0;
    int lh = check(node.left);
    if (lh == UNBALANCED) return UNBALANCED;
    int rh = check(node.right);
    if (rh == UNBALANCED) return UNBALANCED;
    if (Math.abs(lh - rh) > 1) return UNBALANCED;
    return 1 + Math.max(lh, rh);
}

static boolean isBalanced(TreeNode root) {
    return check(root) != UNBALANCED;
}

If a sentinel feels too clever, return a small record of (balanced, height) instead. It is clearer and slightly slower, and it removes the dependence on the height convention. Whatever you choose, keep the early return: without it the function still runs in O(n) but loses the ability to stop at the first failure.

When recursion is the bug: degenerate trees

Recursion depth equals tree height, and the trees you most need to check are the ones whose height has run away. A binary search tree fed sorted keys without rebalancing becomes a chain of n nodes. CPython's default recursion limit is 1,000 frames; running is_balanced on a 5,000-node left-leaning chain raised RecursionError: maximum recursion depth exceeded. The function descends the left chain to the bottom before it can compare any heights, so the early return does not help. In Java the equivalent is a StackOverflowError at a depth that depends on the thread's stack size.

The robust version is an explicit-stack post-order traversal. Each node is pushed twice: once to schedule its children, and once to be processed after they are done.

def is_balanced_iterative(root):
    if root is None:
        return True
    heights = {None: 0}
    stack = [(root, False)]
    while stack:
        node, children_done = stack.pop()
        if children_done:
            lh, rh = heights[node.left], heights[node.right]
            if abs(lh - rh) > 1:
                return False
            heights[node] = 1 + max(lh, rh)
        else:
            stack.append((node, True))
            if node.right is not None:
                stack.append((node.right, False))
            if node.left is not None:
                stack.append((node.left, False))
    return True

This returned False on a 200,000-node chain without trouble, and agrees with the recursive version on trees A and B. It uses O(n) memory for the height map in the worst case. If memory matters, store the height in a field on the node, or pop child heights from a second stack, which brings auxiliary space back to O(h). The general technique of turning recursion into an explicit stack is covered in the BFS and DFS guide, and Morris traversal shows how far you can push constant-space traversal when the tree can be temporarily modified.

Height-balanced, AVL and red-black are different contracts

The check above tests one particular invariant. Self-balancing trees each maintain their own, and confusing them causes false alarms in tests.

A valid red-black tree can have one subtree roughly twice as tall as its sibling, so asserting height-balance on a red-black implementation's output will fail on correct code. If you are testing a red-black tree, check its own invariants, plus the BST ordering, which height-balance says nothing about. Balance is a shape property; ordering is a separate check, and a tree can pass one and fail the other. For an ordering-dependent query on a BST, see the k-th smallest element in a BST.

Variations you will meet

• Return the offending node. Instead of -1, return the first node that fails along with a flag. This is what you want in a debugging tool or a test assertion message, because "unbalanced" alone does not tell anyone where to look.
• Tolerance k. Some structures allow a height difference up to k. Replace the constant 1 with k; the algorithm and its complexity are unchanged.
• Minimum and maximum depth. A different notion compares the shallowest and deepest leaf. It is easy to confuse with height-balance; a tree can satisfy one and not the other, so name which one you mean in specifications.
• Incremental checking. If the tree changes often, store the height at each node and update it on the path from a modified node to the root. That is O(h) per update and is precisely what an AVL tree does before deciding whether to rotate.
• N-ary trees. Generalise to the maximum minus the minimum of the children's heights, with care over whether a missing child counts as height 0.

Failure modes and testing

Most wrong answers come from a handful of mistakes. Checking only the root misses imbalance lower down, as the two-chain example shows. Mixing height conventions, such as an empty tree at -1 with a sentinel of -1, makes an empty subtree look like a failure. Forgetting to propagate the sentinel, by computing 1 + max(lh, rh) when one side is -1, turns failure into a plausible height and hides it. Measuring depth from the root instead of height from the leaves inverts the comparison. And recursion on unbounded input fails in production rather than in tests, because test trees are small.

A good test set is short: the empty tree; a single node; trees A and B above; the two-chain tree that fools a root-only check; a perfect tree of depth 15 or so; and a long chain to exercise the iterative path. Add a property test that builds random trees, compares the linear check against the naive one, and asserts they agree. The naive version is slow but obviously correct, which makes it a good oracle.

Where this matters outside interviews

Database and file-system indexes rely on balanced trees, usually B-trees rather than binary ones, and their test suites assert their own balance invariants after every operation. In-memory ordered maps in standard libraries are typically red-black trees. Code that builds trees from data, such as parse trees, decision trees or Huffman trees, is not balanced by design, and a balance check there is a diagnostic: a tree much deeper than expected predicts slow lookups or a stack overflow later. The general lesson carries over: compute bottom-up, carry failure in the return value, and replace recursion with an explicit stack when depth is not under your control.

What to do next

1. Implement check with the sentinel and the early return, and confirm it on trees A and B by hand before running it.
2. Write the naive version as a test oracle and add a randomized test that compares the two on a few thousand trees.
3. Add the iterative version and run both on a 100,000-node chain to see the recursive one fail and the iterative one succeed.
4. Extend the function to return the first failing node, and use it in an assertion message.
5. If you maintain a red-black or other self-balancing tree, write a validator for its own invariants rather than reusing this check.
6. Read the AVL rotation rules next, which use exactly these stored heights to restore balance after an insert.