Recursion as Structural Induction

The recursive definition does the work

In most curricula, recursion is introduced on linear data (factorial, Fibonacci, sum of an array) where iteration would have been simpler. Students conclude, correctly, that recursion is an exotic alternative to a loop. Trees invert that impression. A loop over a tree requires an explicit stack; a recursive function over a tree requires only the base case and the recursive case, both of which fall out of the tree's definition.

The node type is two fields and a reference:

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

An empty tree is None. A one-node tree is Node(v). A three-node tree is Node(v, Node(l), Node(r)). Every function on a tree will have the same shape: check for None first, then recurse into left and right, then combine.

The three traversals

Pre-order visits the node, then the left subtree, then the right. In-order visits left, then node, then right. Post-order visits left, then right, then node. These are not three different algorithms, they are the same algorithm with one line moved. But the choice of when to process the node determines what the traversal is good for.

def preorder(node):
    if node is None: return
    visit(node)             # process first - top-down
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if node is None: return
    inorder(node.left)
    visit(node)             # process between - yields sorted BST output
    inorder(node.right)

def postorder(node):
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    visit(node)             # process last - bottom-up

Pre-order is for copying or serialising trees. In-order is for binary search trees, it produces keys in sorted order, which is itself the definition of a BST. Post-order is for anything where the answer at a node depends on answers from its subtrees: heights, deletion, expression-tree evaluation.

Returning information up the stack

The single most transformative insight in this module is that the return value of a recursive function is not "the answer for the whole tree", it is "the answer for this subtree." The parent then combines those answers. Consider the height of a tree:

def height(node):
    if node is None: return -1          # empty tree: by convention, -1
    return 1 + max(height(node.left), height(node.right))

Read it as a structural induction. The height of the empty tree is −1 (so that a single leaf has height 0). The height of a non-empty tree is one more than the taller of its two children. That's the recursive case. Once you write the two cases, you are done, there is no "edge case at the root" to worry about, because the root is just another node.

The same shape powers diameter, balanced-check, lowest-common-ancestor, and every "maximum path sum" variant. When stuck on a tree problem, ask: "what must each node return to its parent so the parent can answer the question?" That single reframing solves most of them.

Binary search trees

A BST is a binary tree with the extra invariant that, 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 in-order traversal of a BST yields sorted values, in fact, that property is often used as the defining characteristic.

Balanced BSTs (AVL, red-black, treap) guarantee that all operations run in O(log n). Unbalanced BSTs can degenerate to O(n) in the worst case: inserting sorted values into an ordinary BST produces a degenerate tree that is effectively a linked list. Production languages ship balanced variants (TreeMap in Java, std::map in C++, SortedDict in Python's sortedcontainers) because unbalanced ones are unreliable.

Heaps

A heap is a binary tree with a weaker invariant: the value at every node is smaller than (min-heap) or greater than (max-heap) the values of its children. There is no ordering between siblings. This looser constraint allows a heap to be stored as a flat array, a node at index i has children at 2i + 1 and 2i + 2, which is why heap operations are cache-friendly and why Python's heapq module works on plain lists.

The two operations are push (add to the end, sift up) and pop (swap first and last, remove last, sift down). Both run in O(log n). Building a heap from an unordered array runs in O(n), not O(n log n), a counterintuitive result that falls out of a careful accounting of sift-down costs at each level.

Complexity, reasoned

Traversal of a tree with n nodes is always O(n), each node is visited once, each visit does constant work excluding the recursion. Space is O(h) on the call stack, where h is the height. For a balanced tree, that's O(log n); for a degenerate one, O(n), which can overflow for large inputs. Balanced BST insertion, deletion, and lookup are O(log n) deterministic. Heap push and pop are O(log n); peek is O(1). The heapify construction from an unordered array is O(n).

When to reach for a tree

Binary search trees are for ordered key-value storage where you need not just lookup but also range queries, predecessors, successors, and in-order iteration. A hash map outperforms a BST on pure lookup but cannot answer "give me the smallest key greater than X". Heaps are for priority queues, anywhere you want the min or max of a dynamically-changing set and do not need the full ordering. For representation of hierarchical relationships (file systems, DOM, expression parsing) a general tree (not a BST) is the natural model.

Where beginners go wrong

• Reading recursion as magic. The call stack is a real machine. Every recursive call pushes a frame; returning pops one. If you can trace three levels of recursion on paper, the rest follows.
• Forgetting the base case. if node is None: return is not decoration. It terminates the recursion and often carries the "empty tree" answer (e.g., height −1, sum 0, min infinity).
• Confusing recursion with backtracking. Tree recursion returns once per call. Backtracking explores alternatives and undoes them. Both use the call stack; they are not the same pattern.
• Assuming a BST is balanced. The textbook BST is not self-balancing. Inserting sorted keys will produce a linked list. Use the language's balanced implementation in production.

What to read next

Continue with Module 06 · Dynamic Programming, which formalises the idea of "return the subtree's answer to its parent" as a general recurrence. Graphs in Module 07 generalise trees to arbitrary structures; everything you learn here carries forward.