Trees, asked five ways

Six numbers in a chart: 8 at the top, 3 and 10 under it, then 1, 6 and 14. This lesson asks that one small tree five different questions.

Before you start. A binary search tree is a chart of boxes (nodes) where each box has at most two boxes below it, every smaller number sits somewhere down its left side and every bigger one down its right; Trees (BST, balancing, heaps, tries) built it, and Trees, Worked (rotations, B-trees, range trees) showed how it is kept short. You also need a function that calls itself on a smaller copy of the problem and waits for the answer, which is all recursion is (Recursion & Dynamic Programming).

The idea in 30 seconds

A tree question is answered by messages between neighbours: what each node is told by the node above it, and what it reports to the node above it.
Checking a search tree needs the allowed range carried down from above; checking each node against only its own two children lets a misplaced value through.
The lowest common ancestor of two values is the first node that hears “found” from both of its sides, reported up from below.
Level order lists a tree row by row, either by carrying the depth down or by a waiting line that takes each node and adds its children to the back.
Preorder (node first) plus inorder (left side, node, right side) fix a tree’s shape exactly: preorder names each subtree’s top, inorder splits its sides.
A tree can be written as one line by preorder with a mark for every empty spot, and read back in the same order.

Read the story · Skip to the numbers