Balanced Binary Tree and Maximum Depth: The O(n) Check

Two of the first tree questions anyone meets are "what is the maximum depth of this binary tree?" and "is this binary tree height-balanced?" The first is a three-line recursion. The second looks like the first plus one comparison, and the obvious way to write it is correct but recomputes the same heights over and over. The fix is a small change in what the recursion returns, and it is a pattern you will use for every "compute something about each subtree" question.

The problem it solves

Height (or maximum depth) is the number of nodes on the longest path from the root down to a leaf. In the lesson's convention an empty tree has height 0 and a single leaf has height 1. A binary tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most one.

These definitions matter beyond the interview. Every operation on a binary search tree walks one root-to-leaf path, so height is the bill for search, insert and delete. A balanced tree of n nodes has height around log n. A tree built by inserting sorted keys degenerates into a chain of height n, and then it is a linked list with extra pointers. Self-balancing trees, such as AVL trees, exist to keep that height near log n, and the AVL invariant is exactly this balance check.

The intuition

Height is defined recursively, so it is computed recursively: the height of a node is one more than the taller of its two children, and None has height 0. Each call does constant work and every node is visited once, so it is O(n).

The balance check is where the trap is. The definition says "at every node", which suggests: at the root, compute both heights, compare them, then recurse into each child and do the same. That is correct, but each height call walks the entire subtree, and every node is walked again once for each of its ancestors. On a balanced tree that totals O(n log n).

The better version notices that height is computed bottom-up anyway. Make one recursion return the height and the verdict together. A common encoding uses -1 to mean "unbalanced somewhere below": if either child returns -1, or the two heights differ by more than one, return -1; otherwise return the real height. Each node is visited once and the check is O(n).

A subtle point: comparing only the root's two sides is not enough. Both sides can have similar heights while a node deep inside one of them is lopsided, which is why "at every node" is part of the definition.

Watch it run

The animation starts with two trees holding the same three values: one is a pyramid, one is a chain wearing a tree costume. It defines height as the longest link count down to a leaf, where a leaf itself has height 1. In full, both sides return 1, so the root is 1 + max(1, 1) = 2. In skew, every node has one child all the way down, so the height is 3 for exactly the same three values. Then balance: every node's two sides must differ by at most 1. At full's root the difference is |1 − 1| = 0, which passes. At skew's root the left side is empty, height 0, and the right side is 2, so the difference is 2 and the check fails. The last frame makes the point: height is the bill for every operation, around log n when balanced and n for a skewed tree, which behaves like a linked list.

The code

The lesson's height and top-down balance check, on the animation's two trees:

class Node:
    def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

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

def is_balanced(n):
    if n is None: return True
    gap = abs(height(n.left) - height(n.right))    # sides may differ by 1 at most
    return gap <= 1 and is_balanced(n.left) and is_balanced(n.right)

full = Node(2, Node(1), Node(3))
skew = Node(1, None, Node(2, None, Node(3)))       # a chain wearing a tree costume
print(height(full), is_balanced(full))   # 2 True
print(height(skew), is_balanced(skew))   # 3 False

The one-pass version returns the height or -1, and stops as soon as any subtree fails. The tricky tree shows why every node must be checked: the root's sides differ by only 1, but the left child is lopsided:

def balanced_height(n):
    """Height of n, or -1 as soon as any subtree is unbalanced."""
    if n is None:
        return 0
    left = balanced_height(n.left)
    if left == -1:
        return -1                                   # stop: already failed below
    right = balanced_height(n.right)
    if right == -1 or abs(left - right) > 1:
        return -1
    return 1 + max(left, right)

def is_balanced_fast(n):
    return balanced_height(n) != -1

print(is_balanced_fast(full), is_balanced_fast(skew))   # True False

# Both sides have height 2, yet the left child itself is lopsided.
tricky = Node(1, Node(2, Node(3, Node(4))), Node(5, Node(6)))
print(abs(height(tricky.left) - height(tricky.right)), is_balanced_fast(tricky))   # 1 False

Counting the calls the top-down check makes on perfect trees shows the repeated work. The count grows about log n times faster than n:

calls = 0
def counted_height(n):
    global calls
    calls += 1
    return 0 if n is None else 1 + max(counted_height(n.left), counted_height(n.right))

def naive_balanced(n):
    if n is None: return True
    ok = abs(counted_height(n.left) - counted_height(n.right)) <= 1
    return ok and naive_balanced(n.left) and naive_balanced(n.right)

def perfect(depth, v=0):
    if depth == 0: return None
    return Node(v, perfect(depth - 1, 2 * v + 1), perfect(depth - 1, 2 * v + 2))

for d in (10, 14):
    calls = 0
    naive_balanced(perfect(d))
    print(2 ** d - 1, calls)
# 1023 18434
# 16383 425986

Maximum depth can also be found level by level with a queue, which avoids recursion on very deep trees:

from collections import deque

def max_depth_bfs(root):
    depth, level = 0, deque([root] if root else [])
    while level:
        depth += 1
        for _ in range(len(level)):                 # one full level per round
            n = level.popleft()
            level.extend(c for c in (n.left, n.right) if c)
    return depth

print(max_depth_bfs(full), max_depth_bfs(skew), max_depth_bfs(None))   # 2 3 0

All of it checked against the definition, applied at every node, on 3,000 random trees of up to 25 nodes, including the empty tree:

import random

def random_tree(size):
    if size == 0: return None
    left = random.randint(0, size - 1)
    return Node(size, random_tree(left), random_tree(size - 1 - left))

def brute_balanced(n):
    # every node, checked straight from the definition
    nodes, stack = [], [n] if n else []
    while stack:
        x = stack.pop()
        nodes.append(x)
        stack += [c for c in (x.left, x.right) if c]
    return all(abs(height(x.left) - height(x.right)) <= 1 for x in nodes)

random.seed(22)
ok = True
for _ in range(3000):
    t = random_tree(random.randint(0, 25))
    b = brute_balanced(t)
    ok &= is_balanced(t) == b and is_balanced_fast(t) == b
    ok &= height(t) == max_depth_bfs(t)
    ok &= balanced_height(t) == (height(t) if b else -1)
print(ok)                                           # True

The complexity

• Height: O(n) time, O(h) stack space for the recursion, where h is the height.
• Top-down balance check: O(n log n) on a balanced tree, because each node is measured once per ancestor. The 1,023-node tree above needed 18,434 calls.
• One-pass check: O(n) time, O(h) space. It also exits early on the first failure.
• BFS depth: O(n) time, O(w) space for the widest level.

Where it goes wrong

• Checking only the root. The tricky tree passes at the root and fails one level down.
• Mixing conventions. Some problems count edges, so a leaf has height 0. Decide once and make the base case match.
• Confusing balanced with complete or perfect. A balanced tree may have gaps; a complete tree fills every level left to right.
• Deep recursion. A skewed tree of 100,000 nodes exceeds Python's default recursion limit. Use the BFS version or an explicit stack.

When it shows up in interviews

"Maximum depth of a binary tree" is a standard warm-up and "balanced binary tree" its usual follow-up, where the interviewer asks for the complexity of your first answer and then for an O(n) one. The return-two-things-from-one-recursion idea is the same one behind the diameter of a binary tree, and the level loop is level order traversal. Balance is also why search in a binary search tree is only O(log n) when the tree stays shallow.

How to say it in an interview

"Height is one plus the taller child, with None at zero, so it is an O(n) recursion. For balance, calling height at every node recomputes subtrees and costs O(n log n). Instead I compute height bottom-up and use -1 as a signal: if either child is -1, or their heights differ by more than one, I return -1, otherwise the real height. One visit per node, O(n) time and O(h) stack space. For a very deep tree I would switch to an iterative traversal."