Recursion as Structural Induction

Why "return up the stack" is the whole module

Most students learn recursion on linear data, factorial, Fibonacci, sum of an array. Those problems work, but they encourage a wrong intuition: that recursion is for cases where you could've used a loop. Trees flip that. The recursive structure of a tree (a node plus two subtrees) is the structure of the algorithm. Iteration would require an explicit stack and obscures the elegance.

The skill that takes a beginner from "I can solve maximum depth" to "I can solve maximum path sum" is reframing the recursion: the function returns one thing (what the parent needs) and updates a global tracker for the actual answer when the question requires it. Many tree problems use this two-output structure; the rest use a single output that propagates up the stack to the root.

The universal template

def solve(node):
    if node is None:
        return base_value             # what the empty tree contributes
    left  = solve(node.left)          # recurse
    right = solve(node.right)
    return combine(left, right, node) # combine

Three lines after the base case. The variations sit in combine. Below are six classic problems written against this template; the only differences are the base value, the combine function, and (sometimes) a global update.

Maximum depth

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

Base value: 0 (empty tree has no nodes). Combine: 1 + max of children's depths. The root's depth is the answer to the global question. No global tracker needed.

Balanced binary tree

def is_balanced(node):
    def height(n):
        if n is None: return 0
        l = height(n.left)
        if l == -1: return -1            # propagate failure
        r = height(n.right)
        if r == -1: return -1
        if abs(l - r) > 1: return -1
        return 1 + max(l, r)
    return height(node) != -1

Trick: the function returns the subtree's height, but uses -1 as a sentinel to signal "this subtree is unbalanced". Two outputs in one return value. The early returns short-circuit work as soon as imbalance is found anywhere in the tree.

Diameter

"Diameter" is the longest path between any two nodes (measured in edges). The path may not pass through the root.

def diameter(root):
    best = [0]                          # global tracker (boxed for closure)
    def depth(n):
        if n is None: return 0
        l = depth(n.left)
        r = depth(n.right)
        best[0] = max(best[0], l + r)   # path through n: l + r edges
        return 1 + max(l, r)            # what parent needs: depth from n
    depth(root)
    return best[0]

Two outputs again. The return value is the depth, what the parent needs to compute its own depth. The global tracker captures the longest path that passes through the current node, which equals l + r (left depth + right depth, both counted in edges).

The pattern: when the answer is not the root's return value but a maximum-over-all-nodes of some local quantity, use a global tracker. Recurse normally, update the tracker at each node, return what the parent needs.

Lowest common ancestor

def lca(node, p, q):
    if node is None or node is p or node is q:
        return node                       # found one or hit the boundary
    left  = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node                       # p and q split here - node is the LCA
    return left or right                  # both on one side, propagate up

Read it as a state machine. Each call returns either p, q, the LCA, or None. If both children return non-null, the current node is where p and q diverge, return node. If only one child returns non-null, propagate it up. If both are null, we haven't found anything yet, return null.

The base case node is p or node is q is the trick. We return the node itself when we find p or q; the parent then looks at the two return values to decide whether the LCA is at this level or higher.

Binary tree maximum path sum

Find the path with the largest sum, where a path is any sequence of connected nodes (no need to start at a leaf or pass through the root). Hard because paths can take "hairpins", go up one branch, hit a node, go down the other branch.

def max_path_sum(root):
    best = [float('-inf')]
    def gain(n):
        if n is None: return 0
        # Use the children's gains only if positive - negatives drag down our path.
        l = max(0, gain(n.left))
        r = max(0, gain(n.right))
        # Path that turns at n: include both children plus n.
        best[0] = max(best[0], n.val + l + r)
        # What the parent can extend: pick at most one child.
        return n.val + max(l, r)
    gain(root)
    return best[0]

Two outputs at full force. The return value is "the best straight-line gain extending up from this node", the parent can attach this to its own value plus possibly the parent's other child. The global tracker captures "the best path that turns at this node", both children plus this node. The max(0, …) guard prevents negative branches from dragging down the path.

If you understand this pattern, you can write any tree-DP problem on demand. The structure is invariant; only the local computation changes.

Validating a BST

A BST has the invariant: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. The naïve check ("left child < node < right child") fails on trees where a deep right descendant of a left subtree is greater than the root.

def is_valid_bst(root):
    def check(n, lo, hi):
        if n is None: return True
        if not (lo < n.val < hi): return False
        return check(n.left, lo, n.val) and check(n.right, n.val, hi)
    return check(root, float('-inf'), float('inf'))

The recursion threads bounds down the tree: every left descendant must be less than the current node; every right descendant must be greater. The bounds tighten as we go down. Each node is checked against its full ancestral context, not just its parent.

Recognising the pattern

Reach for the return-up-the-stack template whenever the answer at a node depends on what's true about its subtrees. Variations:

• Single-output recursion when the answer is the root's return value (max depth, sum of nodes, count of nodes).
• Two-output recursion (return + global) when the answer is "the maximum/minimum/best of some local quantity over all nodes" (diameter, max path sum, longest zigzag).
• Bounded recursion when the validity at a node depends on inherited constraints from ancestors (BST validation, range queries).

If the problem is "do something to every node" (modify, count, traverse), it's a straightforward in-order/pre-order/post-order traversal, no return value needed. If the problem is "find the best subtree" or "compute a property of the tree", it's the template above.

Where beginners go wrong

• Confusing the return value with the answer. In max-path-sum, the return is "best straight-line gain", not "max path sum". Returning the wrong quantity gives wrong answers on trees where the best path turns somewhere internal.
• Forgetting the max(0, …) guard. Negative subtree contributions don't help; including them gives smaller answers. The guard is the difference between "best path that uses this branch" and "best path that may skip this branch".
• Validating a BST by comparing only with the parent. A deep descendant can violate the invariant without violating the immediate parent-child relation. Pass bounds down.
• Using a Python list as a "boxed int" without understanding why. Python's closures cannot rebind outer-scope ints; best = 0; def f(): best = 5 creates a new local. best = [0]; def f(): best[0] = 5 mutates the list and works. Other languages don't have this quirk.
• Returning before recursing. Subtle bug: writing if some_condition: return early before the recursive calls means subtrees are never explored, the global tracker stays uninitialised.

What to read next

The Trees module ties this concept to traversals and BSTs. Dynamic Programming generalises "return up the stack" to recurrences over arbitrary structures, tree DP is one shape; sequence DP is another.