Trees: Recursion That Bubbles Up

A tree is a recursive shape

A binary tree is a hierarchy where every node has up to two children. The definition is itself recursive: a tree is a root plus two smaller trees (its left and right subtrees), where an empty tree — null — is the base case.

That is why almost every tree solution is recursion with the same skeleton:

def solve(node):
    if node is None:
        return base_value          # empty tree: the easy answer
    left = solve(node.left)        # trust recursion on the smaller trees
    right = solve(node.right)
    return combine(left, right, node)

The mental move that makes trees click: do not trace the recursion. Assume solve already works on the children — it does, by induction — and only ask "given correct child answers, how do I combine them?" Maximum depth is the whole method in three lines: return 1 + max(depth(left), depth(right)), base case 0.

The three DFS orders are one walk

Depth-first search (DFS) means going as deep as possible before backing up. The three traversal orders — preorder, inorder, postorder — are the same walk; the only difference is when you process the current node relative to the two recursive calls:

On this tree:

      4
     / \
    2   6
   / \
  1   3

preorder gives 4 2 1 3 6, inorder gives 1 2 3 4 6, postorder gives 1 3 2 6 4. Notice the skeleton above is postorder — child results before combining — which is why postorder thinking dominates interview problems.

Pattern 1: return a value, track a global

Here is the pattern behind Diameter of Binary Tree, Binary Tree Maximum Path Sum, and Balanced Binary Tree — the single most-tested tree idea.

Sometimes the value you must return to the parent is not the value you are looking for. Diameter asks for the longest path between any two nodes. At each node, the best path through it is left_height + right_height. But you cannot hand that to your parent — a path that already bends through you cannot bend again higher up. The parent only needs your height.

So: return one thing, record another on the side.

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        best = max(best, lh + rh)      # candidate answer: path bending here
        return 1 + max(lh, rh)         # what the parent actually needs
    height(root)
    return best

Worked numbers on the tree above: node 2 has child heights 1 and 1, so it records candidate 2 and returns height 2. The root has child heights 2 and 1 — candidate 3 (the path 1..2..4..6 or 3..2..4..6), returns 3. Answer: 3 edges.

The same shape solves Balanced Binary Tree (return height, flag imbalance when child heights differ by more than 1 — or return -1 as an "unbalanced" signal to short-circuit) and Maximum Path Sum (return the best downward gain, record the best bent path; clamp negative child gains to 0 because taking a negative branch never helps).

Pattern 2: pass state down

The mirror pattern: some questions need information that flows from the root downward as extra function arguments.

Count Good Nodes asks how many nodes are >= every ancestor on their path. Each node needs one fact from above: the maximum value seen so far on the way down.

def count_good(node, path_max):
    if not node:
        return 0
    good = 1 if node.val >= path_max else 0
    new_max = max(path_max, node.val)
    return good + count_good(node.left, new_max) + count_good(node.right, new_max)

Path Sum problems pass the remaining target down; BST validation passes allowed bounds down (next BST lesson). Choosing between the two patterns is one question: does this node need to know about its ancestors (pass down) or its descendants (return up)? Hard problems often need both at once — that is precisely what diameter does (heights bubble up, the answer is tracked globally).

BFS: the queue and the level snapshot

Breadth-first search (BFS) visits the tree level by level instead of branch by branch, using a queue (first in, first out). The interview version has one crucial detail: snapshot the queue size before draining a level, so you know where one level ends and the next begins.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):     # exactly this level's nodes
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Without the size snapshot, children mix into the current level and per-level output is impossible. Level-by-level structure answers Right Side View (last node of each level), zigzag order, and level averages with the same loop.

Choosing BFS vs DFS: anything phrased "level", "closest to the root", or "minimum depth" wants BFS. Anything computed from subtree results wants DFS. Both visit all n nodes in O(n); DFS holds O(h) stack frames (h = height), BFS holds up to a whole level — O(n) for a bushy tree's bottom level.

Complexity habits

Time is almost always O(n) — every node visited once. Space is the recursion stack: O(log n) on a balanced tree, O(n) on a degenerate chain shaped like a linked list. Saying "O(h), which is log n balanced, n worst case" is the expected answer, and interviewers listen for it.