Tree Problems Are Recursion Problems

"Here's the whole track in one sentence: because a tree is made of smaller trees, almost every tree problem is solved by 'handle this node, and trust recursion to handle the children.' Learn that template and you've learned tree algorithms."

The Template Behind Almost Everything

You saw it in counting, height, and traversal: tree algorithms share one shape. It's two parts:

Base case — what to return for an empty subtree (usually 0, None, or True). This stops the recursion.
Recursive case — recurse on the left subtree, recurse on the right subtree, then combine their answers with this node's own value.

That's it. Height combines with 1 + max(left, right). Sum combines with node.val + left + right. Count combines with 1 + left + right. "Is balanced" combines by checking the two subtree heights differ by ≤1. The structure is self-similar, so the solution is: solve the node, recurse on the subtrees, combine. Different problems just change the combine step.

The Leap of Faith

The mental trick that makes this easy is what the next track calls the recursive leap of faith: when writing the function, assume the recursive calls already work correctly on the smaller subtrees, and only worry about combining their results for the current node. Don't try to trace the whole recursion in your head — that way madness lies. Trust that height(node.left) returns the correct left height, and just write the one combine step. The base case guarantees the recursion bottoms out, and induction does the rest. This single mindset shift turns tree problems from intimidating to almost mechanical.

Tree algorithm template: handle the base case (empty subtree), then recurse left, recurse right, and combine with this node. Different problems only change the combine step. Trust the recursive calls — the leap of faith — instead of tracing the whole tree.

When Recursion Bites Back

One caution carried from the Complexity track: recursion uses the call stack, O(height) deep. On a balanced tree that's O(log n) — totally fine. But on a degenerate, unbalanced tree (height ≈ n), deep recursion can hit Python's recursion limit and crash with RecursionError. For trees that might be pathologically deep, you convert the recursion to iteration with an explicit stack (the stack/recursion equivalence from the Stacks track). For balanced trees — the normal case — recursion is clean and safe. Know the failure mode so it never surprises you in production.

Pippa's Confession

I used to try to mentally simulate the entire recursion — every call, every return — and my brain would melt around depth three. Dad stopped me: "Don't trace it. Assume the children's answers are correct, and just write how this node combines them." The leap of faith felt like cheating, but it's the whole discipline of recursion: solve one level honestly, trust the rest by induction. Tree problems went from terrifying to a fill-in-the-blank template the day I let go of tracing.

Code

Four tree functions, one recursive template·python

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

root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5)))

# Notice: EVERY function is base case + recurse-left + recurse-right + combine.
def height(n):
    if n is None: return -1                          # base case
    return 1 + max(height(n.left), height(n.right))   # combine

def total(n):
    if n is None: return 0                            # base case
    return n.v + total(n.left) + total(n.right)        # combine

def count_leaves(n):
    if n is None: return 0                            # base case
    if not n.left and not n.right: return 1            # a leaf
    return count_leaves(n.left) + count_leaves(n.right)

def is_balanced(n):
    def check(n):                                      # returns height, or -1 if unbalanced
        if n is None: return 0
        lh = check(n.left)
        rh = check(n.right)
        if lh == -1 or rh == -1 or abs(lh - rh) > 1: return -1
        return 1 + max(lh, rh)                          # combine
    return check(n) != -1

print(height(root), total(root), count_leaves(root), is_balanced(root))
# 2 21 3 True — four problems, one template, only the combine step changes.

Exercise

Using the template (base case + recurse left + recurse right + combine), write a function that returns the MAXIMUM value stored anywhere in a binary tree. State your base case and your combine step explicitly. Then say what the recursion depth (and thus stack usage) would be on a balanced tree versus a degenerate one-sided tree of n nodes.

Hint

Base case: an empty subtree returns negative infinity. Combine: max(node.v, max_in(left), max_in(right)). Depth is O(log n) on a balanced tree (safe) but O(n) on a degenerate chain — which can hit Python's recursion limit.

The Template Behind Almost Everything

The Leap of Faith

When Recursion Bites Back

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0