Trie (Prefix Tree)

A tree keyed by characters, where the path from the root spells a prefix: lookup, insert and prefix search in time proportional to the word length, not the number of words.

Overview

A trie stores strings as paths. The root is the empty string; each edge adds one character; a node is marked when the path to it is a whole word. To look up a word you walk one edge per character, so the cost depends on the length of the word (call it L) and not on how many words are stored. The name comes from retrieval; Edward Fredkin described the structure as trie memory in 1960.

A hash set also finds a word in about O(L) time, because hashing reads every character. What the hash set cannot do is answer a prefix question: every word starting with ca is one walk in a trie and a full scan in a hash set. Prefix questions are why tries exist: autocomplete, spell checking, longest-prefix matching in routers, and word counting by prefix.

Hash set — O(L) — O(n): scan everything — No — Low: one entry per word
Sorted array — O(L log n) — O(log n) to find the first, then scan the run — Yes — Lowest
Trie — O(L) — O(L) to reach the prefix node, then the subtree — Yes (in-order walk) — High: one node per distinct prefix

The structure

Each node holds its children, keyed by character, and a flag that says a word ends here. A count of words below the node is optional; it makes prefix counts O(L).

A trace: insert cat, car, dog

Each step walks or creates one node. The count column is the number of words that pass through the node after the step.

1 — cat — c — root, c — yes — count(c) = 1
2 — cat — a — c, a — yes — count(a) = 1
3 — cat — t — a, t — yes — is_end(t) = true
4 — car — c — root, c — no, reused — count(c) = 2
5 — car — a — c, a — no, reused — count(a) = 2
6 — car — r — a, r — yes — is_end(r) = true
7 — dog — d, o, g — root, d, o, g — yes, three nodes — is_end(g) = true

Three words of nine characters made seven nodes, because cat and car share ca.

An implementation that runs

The walk is one private method; search and starts_with reuse it. delete walks down, unmarks the word, then walks back up removing nodes that no longer lead to any word.

Every operation is O(L) for a word of length L: one dictionary step per character. delete is O(L) too, because pruning walks the same path back.

Compressed tries

A plain trie spends one node per character, so a long word with no siblings is a chain of single-child nodes. A radix tree (compressed trie) merges each such chain into one edge labeled with the whole substring. Donald Morrison published the binary form as PATRICIA in 1968.

Nodes for interview and internet — 12 — 3
Lookup — One step per character — One comparison per edge; fewer pointer hops
Insert — Create missing nodes — May split an edge where the new word diverges
Good for — Short keys, simple code, interviews — Long keys with few branches: routing tables, URL routers, key-value indexes

The Linux kernel's IPv4 routing table (fib_trie) is an LC-trie: a binary trie over address bits with level compression (a node's child array is indexed by several key bits at once, so one node can have many children) and path compression (bits that form a single path with no branching are skipped).

What you will be able to do

Write insert, search and starts_with from memory and say why each is O(L).
Trace an insert on paper and say how many nodes it creates.
Delete a word without leaving dead nodes behind.
Extend the trie to autocomplete, wildcard search and prefix counts.
Explain when a radix tree beats a plain trie, and when a hash set beats both.

Interview questions

Implement autocomplete: return the top k words for a prefix.
Support wildcard search, where a dot matches any one character.
A trie of a million words uses too much memory. What are the options?
Count the words that start with a given prefix in O(L).
How do you make the trie safe for concurrent readers and writers?