Trees: one thing above, several below

A linked list gives each node one next. Let a node have several, and you have a tree.

The shape#

            8
          /   \
        3       10
       / \        \
      1   6        14

The vocabulary is worth getting straight, because every explanation uses it:

root: the node at the top, 8 here. Exactly one, and it has nothing above it.
child, parent: 3 is a child of 8; 8 is the parent of 3.
leaf: a node with no children. 1, 6 and 14.
height: the longest path from the root down to a leaf. This one is 3.
subtree: any node together with everything under it. 3, 1, 6 is a subtree.

Two rules make it a tree rather than a general graph: every node has exactly one parent except the root, and there are no cycles. That means there is exactly one path between any two nodes.

Why height is the number that matters#

Almost every tree operation costs its height, not its size.

A tree that splits in two at every level holds 1 node at the root, 2 below, then 4, then 8. By height h it holds about 2^h nodes. Turn that round: n nodes fit in a height of about log2(n).

A million nodes fit in a height of 20.

That is the whole appeal. Walking from the root to a leaf of a million-node tree means 20 steps.

The catch#

That only holds if the tree is balanced, meaning its branches are roughly the same depth. Nothing forces that.

Insert 1, 2, 3, 4, 5 into an ordinary binary search tree in order, and each one is larger than everything before it, so each goes to the right:

Height 4 for 4 nodes. You have written a linked list with extra steps, and every operation is O(n) again.

This is why self balancing trees exist, such as AVL and red-black trees. They rearrange themselves on insert to keep the height near log n. The rebalancing rules are fiddly; the thing to remember is why they are there.

Binary search trees#

A binary search tree adds one rule: everything in a node's left subtree is smaller than it, and everything in the right subtree is larger.

Searching becomes a decision at each node. Looking for 6 in the tree at the top: 6 is less than 8, go left. 6 is more than 3, go right. Found. Each step throws away half of what remains, which is binary search made into a shape.

It also means the tree can answer questions a hash table cannot: the smallest key, the largest, everything in a range, and every key in sorted order.

Walking a tree#

Four orders, and the first three differ only in when you handle the node itself.

In order: left subtree, node, right subtree. On a binary search tree this comes out sorted, which is the single most useful fact about them.
Pre order: node, then children. Good for copying a tree, since you make the parent before the children.
Post order: children, then node. Good for freeing or for anything where a node's answer depends on its children.
Level order: everything at depth 1, then depth 2. This is breadth first search, and it needs a queue rather than recursion.

The first three are naturally recursive, and recursion here is just the call stack doing the remembering for you. Swap in a stack you manage yourself and the code is the same shape.

Where trees show up#

File systems. The structure of a parsed program. Database indexes, which are usually B-trees, a flatter relative built for disk. Autocomplete, using a trie. Decision trees. HTML documents.

Common mistakes#

Assuming a binary search tree stays balanced. Sorted input is the worst case, and sorted input is common.
Forgetting the null check on a child before recursing into it.
Confusing height with the number of nodes.
Using in order traversal on a tree that is not a search tree and expecting sorted output.