The problem: autocomplete on every keystroke#
TL;DRthe 30-second version
- A trie stores words as a tree of characters. The path from the root to a node spells a prefix, so every word with that prefix shares that path.
- Prefix lookup costs O(prefix length). The dictionary size drops out. A hash set can't do this at all.
- Autocomplete is: walk to the prefix node, collect the word-ends under it, rank them by frequency, return the top-k.
- The cost is memory. One small node per character plus a pointer per child is cache-unfriendly. Production systems compress it (radix trees, FSTs) and cache the top-k completions on each node.
Why can't a hash set do it? A hash function deliberately scatters keys. 'car', 'care', and 'cart' land in three unrelated buckets, with no hint that one is a prefix of another. The only way to find every key starting with 'car' is to walk the whole table and test each one. That's O(n) per keystroke.
A sorted array does better. Binary-search to the first key at or after 'car', then scan forward while the prefix still matches. That's O(log n + matches) per query, which is fine for a fixed dictionary. But every insert or frequency update has to shift elements, so it's painful to keep current under a live stream of edits.
A trie is built for exactly this. Every word with a given prefix lives under the same node. You walk to that node once, and everything beneath it is a completion. The cost depends on the prefix length, not the dictionary size. Inserts and updates are just as cheap.
The structure: one node per character#
The root stands for the empty string. Each edge carries one character, so the path from the root to a node spells a prefix. A node gets a word-end flag when a complete word stops there. Inserting a word walks down one character at a time, creates any node that's missing, and flags the last one. Insert 'car', then 'cart', then 'care': the second and third reuse the c, a, r nodes and only add one node each.
- root
- c
- a
- r★ word
- t★ word
- e★ word
- r★ word
- a
- d
- o
- g★ word
- o
- c
Now the query. To autocomplete a prefix, walk from the root, one node per character. If any character has no child, the prefix isn't in the dictionary and there are no suggestions. Otherwise you land on the prefix node, and every word-end in its subtree is a completion. Collect them with a depth-first search, sort by frequency (ties broken alphabetically), and return the top-k.
The walk is O(prefix length). Gathering costs as much as the subtree you traverse, and for a short, popular prefix like 'a' that subtree is most of the dictionary. So real systems precompute the top-k completions and store the list on each node. A keystroke then walks to the node and reads the list. The price moves to writes: bumping one word's frequency may have to refresh the cached list on every ancestor up to the root. Production typeaheads rebuild those lists in batch from query logs and accept suggestions that lag by minutes.
PredictA dictionary holds 1,000,000 words. You type the 3-character prefix 'car'. Roughly how many nodes must the trie walk to reach the prefix node?
Hint: The walk cost tracks the prefix length, not the word count.
About 3, one node per character of the prefix. It's the same 3 steps whether the dictionary holds 100 words or 100 million. Gathering the completions underneath is extra work, which is why systems cache the top-k per node.
Complexity: time independent of dictionary size#
Lookup, insert, and delete of a key of length L are all O(L). The cost grows with the key length and not at all with n, the number of keys stored. A balanced binary search tree is O(log n · L) in the worst case, because each of its log n comparisons can touch up to L characters.
| Operation | Cost | Note |
|---|---|---|
| Insert key length L | O(L) | walk/create one node per character |
| Exact lookup | O(L) | walk L nodes, check the word-end flag |
| Prefix walk | O(P) | P = prefix length; n drops out entirely |
| Suggest (no cache) | O(P + S) | S = size of the subtree gathered + sort |
| Suggest (top-k cached) | O(P) | read the precomputed list at the node |
| Space | O(total chars) | minus shared prefixes; plus pointer overhead |
Space is where tries cost you. Shared prefixes are stored once, which is a real saving. But every node carries child pointers and a flag, and there are a lot of nodes. With an array of 26 child slots at 8 bytes per pointer, each node holds 208 bytes of pointers, most of them null. A 256-way byte alphabet pushes that to 2 KB per node. A few million nodes can need gigabytes. A hash map per node stores only the real children, but each child is then a separate allocation reached by pointer-chasing, so cache locality gets worse. Either way, the pointers, not the letters, dominate the memory bill. That is what pushes production systems to the compressed variants below.
If this comes up in an interview#
Why not just use a hash set for autocomplete?
A hash set tests exact membership in O(1) but can't answer 'what starts with car?' at all. Hashing scatters related words to unrelated slots, so the only way to find prefix matches is to scan the entire table. A trie keeps every word with a shared prefix on a shared path, which is exactly what a prefix query needs.
Why is trie lookup O(prefix length)?
The walk follows exactly one node per character of the prefix. 'c' then 'a' then 'r' is three hops. There's no comparison against other keys and no scan of the dictionary, so the number of stored words never enters the cost.
How do you rank suggestions?
Store a frequency on each word-end node, gather the completions in the prefix's subtree, and return the top-k by frequency, breaking ties alphabetically.
What is a radix tree (Patricia tree)?
A compressed trie. Any chain of single-child nodes is merged into one edge labeled with the whole substring. Same prefix queries, far fewer nodes. It's the standard way to cut a plain trie's memory cost, and what Linux routing tables and Redis streams use.
How would you scale a typeahead for the web?
Shard the trie by first letters, serve the precomputed top-k lists from an in-memory cache, and update frequencies asynchronously from query logs. That is what Google's search box and Elasticsearch's completion suggester do.
When to reach for a trie (and when not to)
A trie is the right call when the query is prefix-shaped: autocomplete, typeahead, longest-prefix match, spell-check. It's the wrong call when you only need exact membership, because a hash set is smaller and simpler. And it's the wrong call when the alphabet is huge and the keys are sparse, because the node overhead explodes.
| Trie | Hash set | Balanced BST | Sorted array + binary search | |
|---|---|---|---|---|
| Prefix query | O(P) — native | Not supported (must scan all) | O(log n · L) to locate, then in-order | O(log n + matches) |
| Exact lookup | O(L) | O(L) average (hash + compare) | O(log n · L) | O(log n · L) |
| Insert / update | O(L) | O(L) average | O(log n · L) | O(n) — shift elements |
| Ordered iteration | Yes (DFS in sorted order) | No | Yes (in-order) | Yes (already sorted) |
| Memory | High — pointer per child, many nodes | Low — flat table | Moderate — 2 pointers/node | Lowest — contiguous, no pointers |
Read it as: the hash set wins memory and exact lookup but can't do prefixes. The sorted array wins memory and read-side prefix queries but is painful to update. The trie is the only one where the prefix query is O(prefix length) and updates stay cheap. That is why typeaheads use it.
Compressing the trie, and who uses which
A plain trie's weakness is all those single-child chains and null pointers. Every serious variant attacks that memory cost while keeping prefix lookup.
- Radix tree (Patricia trie): collapse any chain of single-child nodes into one edge labeled with the whole substring. 'r → o → u → t → e' becomes a single edge 'route'. Same prefix queries, far fewer nodes. This is the structure inside Linux's IP routing table (longest-prefix match on a destination address to pick the next hop) and Redis's rax, which backs streams and cluster key-slot tracking.
- Ternary search tree (TST): store children as a small binary search tree keyed by character instead of an array or hash map. Far less memory than a 256-way array, and it supports wildcard search, at the cost of an extra log factor per character.
- DAWG (directed acyclic word graph): a trie that also shares common suffixes by merging identical subtrees. 'fishing' and 'washing' share the trailing 'shing'. Very compact for a fixed dictionary, but it loses easy per-word frequencies and is awkward to update.
- FST (finite-state transducer): a DAWG that also maps each key to a value, such as an offset or a weight. Lucene and Elasticsearch store their entire term dictionary as an FST, in a fraction of the memory of a plain trie.
Where tries hurt
- Memory blow-up. A wide alphabet (256-way byte nodes, or full Unicode) with sparse data leaves most child slots null. Millions of nodes times hundreds of mostly-empty pointers can turn a megabyte of words into gigabytes of trie. Radix compression or a map layout is the defense.
- Cache misses from pointer chasing. Each step of a walk follows a pointer to a node that may live anywhere in memory, so wall-clock time can lag the clean O(L) analysis badly. Contiguous structures (sorted arrays, FSTs) win on locality.
- Top-k cache update cost. Caching completions per node makes a frequency bump cascade up to the root. Under a high write rate this dominates. The usual fix is batched rebuilds from logs, accepting slightly stale suggestions.
- Deletion leaving dead nodes. Removing a word means clearing its end flag and pruning the now-childless nodes back up the path. Skip the prune and the trie fills with dead nodes that waste space and slow walks.
References & further reading
- Fredkin — Trie Memory, Communications of the ACM (1960) — the paper that introduced the trie
- Morrison — PATRICIA: Practical Algorithm To Retrieve Information Coded in Alphanumeric, JACM (1968) — the original radix/Patricia trie
- McCandless — Using Finite State Transducers in Lucene — how Lucene stores its term dictionary as an FST
- Wikipedia — Deterministic acyclic finite state automaton (DAWG) — sharing suffixes as well as prefixes