Recursion: Return Values Up or Pass State Down

Every recursive function moves information in one of two directions. Either the children compute something and return it up for the parent to combine, or the parent passes state down as an argument and the base case reports a finished result. Most tangled recursive code, with a global counter and a list that mysteriously grows, comes from never deciding which way each value travels.

The problem it solves

You can write a working recursion and still not know where the answer is assembled. The recursion basics article covers base cases and unwinding; backtracking covers exploring choices. The question here comes before writing any line: for each value the recursion needs, does it flow from children to parent or from parent to children?

Get it wrong and the symptoms look unrelated: a max_depth variable outside the function, a path list that keeps a sibling's steps, a helper with five parameters when two would do.

The intuition

Ask what a node needs to do its job.

• It needs its children's results: return up. Height, size, sum, "is this subtree balanced": a parent cannot answer until both children have, so the work happens on the way back. The signature stays small, f(node), and the return value carries the answer.
• It needs its ancestors' context: pass down. The path so far, the current depth, a remaining budget, the allowed range of values: a child cannot know these by looking at its own subtree, so the parent hands them over as arguments. The base case already holds a complete result and only reports it.
• It needs both: do both. Checking a binary search tree passes a pair of bounds down and returns a verdict up. That is not a mess; each value still has one direction.

The trouble starts with a value that travels neither way: not an argument, not a return value, but a variable outside the function that every call mutates. The diameter of a binary tree is the classic case where a nonlocal best is a deliberate choice, because the function returns height while the answer is a different quantity. When that happens by accident, it is a bug waiting for a second call.

A useful rule of thumb: if the answer for a node is a function of its subtree, return it up. If it depends on where the node sits, pass it down.

Watch it run

The same tree, 1 with children 2 and 3, and 4 under 2, is asked two different questions; what travels, and which way, decides the shape of the code. Act one returns depths up. A leaf answers immediately: 1, and nothing was handed to it. 2 cannot answer until its children have: 1 + max(1, 0) = 2 goes up. Leaf 3 answers 1. Then 1 + max(2, 1) = 3 goes up from the root. The answer assembled on the way back, and no argument was ever added to the signature.

Act two hands the path down. 1 hands (1) to each child, and the child needs no idea where it sits. 2 hands (1, 2) on. A leaf has the whole path already and just reports it; nothing about the path is combined on the way back, the parents only concatenate the lists. The last frame puts the two shapes together: many recursions use both, bounds going down and a verdict coming up, and a value that travels neither way is the one that ends up a global.

The code

The same question, maximum depth, written both ways, plus the path question with an immutable tuple and with one shared list. The shared-list version only works because of the pop():

import random

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

def depth_up(n):                       # RETURN UP: children answer, parent combines
    if n is None:
        return 0
    return 1 + max(depth_up(n.left), depth_up(n.right))

def depth_down(n, d=1):                # PASS DOWN: each call is told its own depth
    if n is None:
        return d - 1                   # the parent's depth: nothing below it
    return max(depth_down(n.left, d + 1), depth_down(n.right, d + 1))

def paths(n, trail=()):                # pass the path down; the list comes back up
    if n is None:
        return []
    trail = trail + (n.val,)           # a new tuple: siblings never see each other's steps
    if n.left is None and n.right is None:
        return [trail]
    return paths(n.left, trail) + paths(n.right, trail)

def paths_shared(n, trail, out):       # one list for every call: append AND undo
    if n is None:
        return
    trail.append(n.val)
    if n.left is None and n.right is None:
        out.append(tuple(trail))
    paths_shared(n.left, trail, out)
    paths_shared(n.right, trail, out)
    trail.pop()                        # forget this pop and siblings inherit the step

root = Node(1, Node(2, Node(4)), Node(3))
print(depth_up(root), depth_down(root))   # 3 3
print(paths(root))                        # [(1, 2, 4), (1, 3)]
out = []
paths_shared(root, [], out)
print(out)                                # [(1, 2, 4), (1, 3)]

def is_bst(n, lo=float("-inf"), hi=float("inf")):   # bounds go down, a verdict comes up
    if n is None:
        return True
    if not lo < n.val < hi:
        return False
    return is_bst(n.left, lo, n.val) and is_bst(n.right, n.val, hi)

print(is_bst(Node(5, Node(3, None, Node(6)), Node(8))))   # False: 6 sits left of 5

def collect(n, out=[]):                # the default list is built ONCE, at def time
    if n is not None:
        out.append(n.val)
        collect(n.left, out)
        collect(n.right, out)
    return out

print(collect(Node(1)), collect(Node(2)))   # [1, 2] [1, 2]

depth_down still returns something: the deepest depth any leaf was told. Passing down does not forbid returning; it just moves the counting into the argument. The last two lines are the classic trap: a mutable default argument is one list shared by every call and every later top-level call, listed among the traps on the Python cheat sheet.

The seeded check: on 3,000 random trees, both depth functions must agree with a level count done by an explicit stack, both path functions must agree with the stack's root-to-leaf paths, and is_bst must agree with "the in-order values are strictly increasing":

def random_tree(rng, size):
    """Random shape, random values: a tree that is sometimes a BST and often not."""
    if size == 0:
        return None
    left = rng.randint(0, size - 1)
    return Node(rng.randint(0, 20), random_tree(rng, left), random_tree(rng, size - 1 - left))

def by_stack(root):
    """Brute force, no recursion: every root-to-leaf path and the deepest level."""
    found, deepest, stack = [], 0, [(root, ())] if root else []
    while stack:
        n, trail = stack.pop()
        trail += (n.val,)
        deepest = max(deepest, len(trail))
        if n.left is None and n.right is None:
            found.append(trail)
        stack += [(c, trail) for c in (n.right, n.left) if c]   # left popped first
    return found, deepest

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

rng = random.Random(39)
ok = True
for _ in range(3000):
    root = random_tree(rng, rng.randint(0, 12))
    found, deepest = by_stack(root)
    shared = []
    paths_shared(root, [], shared)
    vals = inorder(root)
    ok &= depth_up(root) == depth_down(root) == deepest
    ok &= paths(root) == shared == found
    ok &= is_bst(root) == all(a < b for a, b in zip(vals, vals[1:]))
print(ok)                                   # True

The complexity

Direction does not change the visit count: every version touches each node once, O(n) time, with O(h) stack for height h. It changes the extra cost. A new tuple per call copies the path, O(h) per node; the shared list costs O(1) per step but needs the undo. Concatenating returned lists copies too, which matters only for large outputs.

Where it goes wrong

• Mutating a passed-down list without undoing it. Siblings inherit each other's steps. Use an immutable tuple, or append then pop.
• Mutable default arguments. def f(n, out=[]) shares one list across every call ever made.
• A global for something that could be returned. A counter outside the function breaks the second time you call it, and on concurrent calls.
• Passing down what only the subtree knows. Height cannot be handed to a child; it has to come back up.

When it shows up in interviews

Constantly, because most tree problems are one of the two shapes: maximum depth and balanced trees return up; root-to-leaf paths and path sum pass down; validating a BST does both. Interviewers also ask the follow-up directly: "can you do it without the global?"

How to say it in an interview

"I decide which way each value travels. If a node's answer depends only on its subtree, like height or size, I return it up and combine children on the way back. If it depends on where the node sits, like the path so far or the allowed range, I pass it down as an argument and let the leaf report. Some problems use both, such as BST validation: bounds go down, a boolean comes up. I avoid globals and mutable defaults, and if I share a list, I undo every append."