Trees

How it works

Tree problems are recursion problems. Assume your function already works on the left and right subtrees, then decide how to combine their answers at the current node. If you can state what one call returns to its parent, the code nearly writes itself.

Many questions need two quantities: the value a node reports upward and a global best that may be achieved at that node. Diameter and maximum path sum are the classic cases: each node returns its best downward path, but the answer is the best path that bends through it.

Binary search trees add an ordering invariant. An in-order traversal visits values in sorted order, and every node carries an allowed (low, high) range from its ancestors. Validation, k-th smallest and lowest common ancestor all exploit that.

Breadth-first search is the tool for anything about levels: level averages, right-side view, minimum depth, zigzag order. Process the queue one level at a time by reading its length before the inner loop.

How to attack it

1. 1Decide depth-first (paths, subtree properties) or breadth-first (levels, nearest).
2. 2Define exactly what the recursive call returns for a subtree.
3. 3Write the base case for an empty node first.
4. 4Decide whether a separate global answer is needed beyond the return value.
5. 5Consider recursion depth on a skewed tree and switch to an explicit stack if needed.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

from collections import deque


def max_depth(root):
    # Post-order: answer for a node from its children's answers.
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)   # global answer: a path bending at node
        return 1 + max(l, r)      # value reported to the parent
    height(root)
    return best


def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # exactly one level per outer loop
            node = queue.popleft()
            level.append(node.val)
            queue.extend(c for c in (node.left, node.right) if c)
        levels.append(level)
    return levels

What it costs