Tries & Prefix Trees

A balanced search tree gives us $O(\log n)$ lookups by comparing whole keys to each other. But when the keys are strings, a single comparison is not $O(1)$: deciding whether "international" precedes "internet" already costs five character comparisons, so a BST of $n$ strings of length $L$ really spends $O(L\log n)$ per operation. Worse, the BST throws away an obvious source of structure, namely that "intern", "internet", and "international" all share a prefix, and re-examines those shared characters on every descent.

A trie (from re_trie_val; usually pronounced try) exploits exactly that structure. Instead of comparing keys against each other, it routes each key one character at a time down a tree whose edges are labeled by characters. A root-to-node path spells a prefix; following the characters of a key leads to the unique node that key reaches. Lookup costs $O(L)$, where the work depends only on the key being searched for, never on $n$, the number of stored keys.¹

The structure

The root represents the empty prefix. Note the two-level bookkeeping: a node can exist purely as an interior waypoint (a prefix of some longer key) yet not be a key itself. In the word set $\{\text{to},\text{tea},\text{ted}\}$ the node at path t exists but is not a stored word, so its $isEnd$ is false; the nodes at to, tea, and ted have $isEnd=\text{true}$.

Each node needs a way to find a child by character. Two standard choices:

• Array children. A fixed array of $|\Sigma |$ pointers per node (e.g. 26 for lowercase letters, or children[2] for a binary trie). Child lookup is a single $O(1)$ index, at the cost of $|\Sigma |$ slots per node whether used or not.
• Hash-map children. A char → node map per node, so a node stores only the children it actually has. Smaller for sparse, large alphabets (Unicode), with a small constant-factor hashing overhead.

Operations: all $O(L)$

Insertion walks down from the root, creating a child node whenever the needed edge is missing, and sets $isEnd$ on the final node. Search walks the same path but never creates; it fails the moment a needed edge is absent.

Each loop runs $L$ times and does $O(1)$ work per character (one indexed slot or one hash probe), so insert, search, and the prefix test all run in $O(L)$. startsWith(p) is identical to $\text{Search}$ except it returns true as soon as the path for $p$ exists, ignoring $isEnd$, because any node on a valid path witnesses that $p$ is a prefix of some stored key.

The blue nodes are the six stored words; the white interior nodes (t, te, i) are prefixes shared among them and stored exactly once. Looking up ten visits three edges regardless of whether the trie holds six words or six million.

Space and trade-offs

With array children the worst case is $O(n\cdot L\cdot |\Sigma |)$ pointers: $n$ keys, up to $L$ nodes each, $|\Sigma |$ slots per node. That bound is pessimistic, and tries are far better than it suggests precisely when prefixes are shared: every common prefix collapses to a single path, so a dictionary of English words (densely overlapping) stores far fewer than $n\cdot L$ nodes. Hash-map children replace the $|\Sigma |$ factor with the actual child count, trading a constant for the array's $O(1)$ indexing.

Applications

Autocomplete and prefix search. To offer completions for what a user has typed, walk to the node for the typed prefix in $O(L)$, then DFS the subtree beneath it to enumerate every stored key with that prefix, since the trie has already grouped them.

Wildcard dictionary (the . problem). Design Add and Search Words asks for a dictionary where a query may contain . matching any single character. Plain search no longer follows one path: at a . we must branch into all children and recurse. Concrete characters keep the search $O(L)$; each . multiplies the branching, but the trie still prunes any path that cannot match.

Word search on a board. Word Search II hunts for many dictionary words in a grid simultaneously. Building a trie of all target words lets one DFS over the board carry a trie pointer alongside the grid position: the instant the current board path spells a string that is not a prefix of any target, the missing trie edge prunes the entire branch. One traversal finds all words, and the shared prefixes mean overlapping targets share work.

The binary trie: maximum XOR pair

A beautiful non-string use treats a fixed-width integer as a string of bits over $\Sigma =\{0,1\}$. Maximum XOR of Two Numbers asks for ${\max }_{i,j}(a_i\oplus a_j)$. Brute force is $\Theta (n^2)$; a binary trie solves it in $O(n\cdot b)$ for $b$-bit numbers.

Insert every number bit-by-bit from the high bit down, so each root-to-leaf path of length $b$ is one number. To maximize the XOR of a query $a$ against the stored set, walk down from the root and at each bit greedily steer toward the opposite bit of $a$: a differing bit contributes a $1$ at that (high) position, worth more than every lower bit combined. If the opposite child exists, take it; otherwise follow the only child available. The path traced spells the stored number that maximizes $a\oplus (\cdot )$.

The trie holds $\{010,011,110\}$. For the query $a=100$ the greedy walk wants the opposite bit at each level: $0,1,1$. The high bit of $a$ is $1$, so it takes the $0$-child; the remaining two bits of $a$ are $0$, so at each step the wanted opposite bit $1$ is available and the walk follows it. It lands on the stored number $011$, giving $100\oplus 011=111$, the maximum.

Multi-pattern and compressed variants

A trie of patterns augmented with failure links, pointers that, on a mismatch, jump to the longest proper suffix of the current match that is also a prefix in the trie, is the Aho–Corasick automaton: it scans a text once and reports every occurrence of every pattern in linear time, the multi-string generalization of KMP (which is single-pattern failure-link matching).² For storage, a compressed trie (a radix tree or Patricia trie) contracts each chain of single-child nodes into one edge labeled by a whole substring, shrinking the node count dramatically; suffix trees and suffix arrays push the idea further, indexing all suffixes of a text for fast substring search, the subject of later lessons.³

Takeaways

• A trie is a rooted tree whose edges are labeled by characters; a root-to-node path spells a prefix, and an $isEnd$ flag marks nodes that complete a stored key. Children are an array of size $|\Sigma |$ or a per-node map.
• Insert, search, and startsWith all run in $O(L)$, the key length, and are independent of $n$, beating a BST's $O(L\log n)$.
• Space is up to $O(n\cdot L\cdot |\Sigma |)$ with array children, but shared prefixes are stored once, so prefix-heavy sets compress well; tries beat hash sets by giving ordered traversal, prefix queries, and no collisions.
• Tries power autocomplete, wildcard . matching, and board word-search pruning; over $\{0,1\}$ a binary trie solves maximum-XOR pair by greedily walking toward the opposite bit from the high bit down.
• Aho–Corasick = trie + failure links = multi-pattern KMP; Patricia / radix trees compress single-child chains, and suffix trees / arrays index all suffixes of a text.