Recursion · Divide & Conquer · Binary Trees

A beautiful combination

Recursion is four simple moves. Binary trees are a structure that begs to be walked recursively. Put them together and searching a BST becomes one of the clearest illustrations of the whole recursion method.

The recursion method

Every recursive function does these four things, in this shape. Learn the shape once — it applies to every recursive algorithm you'll ever write.

STEP 01

Break into sub-problem

Reduce the original problem to a smaller instance of itself — one branch of the tree, one element less, half the range.

STEP 02

Call itself

Invoke the same function on the smaller sub-problem. Trust that the recursion will handle it — this is the leap of faith.

STEP 03

Join the solutions

Combine the returned sub-results into the answer for the original problem. Sometimes it's a sum, sometimes it's just passing one up.

STEP 04

Terminating condition

The smallest case, answered directly, no further recursion. Without it, the function never comes back up.

BST search, step by step

A binary search tree already embodies divide-and-conquer: the root's key cleanly splits the world into "smaller on the left, larger on the right." Searching it is just the recursion method, written out literally.

function search(node, key):

STEP 1 — break // reduce to a smaller sub-problem if key < node.key: sub = node.left // smaller keys live left else: sub = node.right // larger keys live right

STEP 2 — recurse // call itself on the sub-problem result = search(sub, key)

STEP 3 — join // in BST search, "join" is trivial: pass the answer up return result

STEP 4 — stop // base cases checked first each call (shown last, lives first) if node is null: return NOT_FOUND if node.key == key: return node // FOUND

Example 1 · search(7)

A successful search. Watch the stack grow as we dive, and then collapse as the "found" result rides back up the chain.

Searching for key = 7

pending

01break

02recurse

03join

04stop

Press play or step to begin the search.

call stack depth 0

empty — search hasn't started

speed

Example 2 · search(5)

An unsuccessful search. The recursion bottoms out at a null child — the other base case. Same four steps, different terminating condition.

Searching for key = 5