Trie Search
Search time depends on the length of the key, not how many keys you've stored — a dictionary of a million words answers in exactly as many steps as the word has letters.
Hands on Interactive visualization
Implementation Code
class TrieNode {
children = new Map<string, TrieNode>();
isEnd = false; // marks a stored word, not just a prefix
}
export class Trie {
private root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
node = node.children.get(ch)!;
}
node.isEnd = true;
}
// One node per character: O(word.length), independent of size.
search(word: string): boolean {
const node = this.walk(word);
return node !== null && node.isEnd; // word, not just prefix
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== null; // same walk, no flag check
}
private walk(s: string): TrieNode | null {
let node = this.root;
for (const ch of s) {
const next = node.children.get(ch);
if (!next) return null; // path breaks
node = next;
}
return node;
}
}Big-O Complexity
m is the key length — lookup cost is independent of the number of stored keys. Space is the pain point: fixed child arrays cost alphabet-size slots per node even when nearly empty; child maps shrink memory but slow each hop. Compressed variants (radix/Patricia tries) merge single-child chains.
In production When to use
Search boxes descend the trie along the typed prefix in O(m), then enumerate the subtree for suggestions — every key sharing that prefix lives below one node, so no scanning of unrelated entries.
Routers store CIDR prefixes in binary tries and walk an address bit by bit, remembering the last node with a route — the deepest match wins. Longest-prefix matching is the trie's signature move.
Dictionary membership is O(word length), and prefix pruning turns Boggle/word-search style DFS from exponential to tractable — abandon a board path the moment its prefix leaves the trie.
Predictive text walks a trie keyed by digit or letter sequences; each keypress advances one node, and the subtree below ranks the candidate completions.
Call-rate tables keyed by dialing prefixes (country/carrier codes) resolve a number to its longest matching prefix — the same longest-prefix walk as IP routing, applied to tariffs.
Aho-Corasick builds a trie of all patterns plus failure links to scan text for thousands of patterns simultaneously in one pass — the engine inside intrusion-detection systems and content filters.
Trade-offs Strengths & weaknesses
- O(m) lookup independent of the number of keys — n can grow without slowing search.
- Prefix queries are structural: all keys with a given prefix sit in one subtree.
- Longest-prefix match falls out of a single walk — awkward or impossible for hash tables.
- No hash collisions, no comparator subtleties: the key's characters ARE the path.
- Shared prefixes are stored once, compressing datasets with heavy prefix overlap.
- Ordered traversal yields keys in lexicographic order for free.
- Memory-hungry: sparse fixed-size child arrays waste most slots; pointer overhead dwarfs the characters stored.
- Cache-hostile — every character hop is a pointer dereference to a scattered node.
- For pure equality lookup of whole keys, a hash table is simpler and usually faster in practice.
- Large or unbounded alphabets (full Unicode) force child maps or bytewise decomposition — more design decisions.
- Deletion must prune now-childless chains upward, which is easy to get wrong.
- Naive tries store one character per node; production uses compressed radix/Patricia variants for real workloads.
Intuition Mental model
The phone-keypad autocomplete tree
Type on a phone keyboard: each letter narrows the suggestions, because the keyboard is walking a tree where every branch is one letter and every path from the root spells a prefix. Words that share a beginning share the same trunk — the tree only splits where the words do.
- The empty search box = the root: every stored word is still possible below you.
- Typing 'c' takes the c-branch = following the child pointer for that character.
- 'ca' then 'car' descend further = each keypress is one O(1) hop; total cost is the word's length.
- Suggestions shown = the subtree below your current node — exactly the words with your prefix, nothing else.
- 'car' lights up as a word while 'ca' doesn't = the end-of-word flag: both are nodes on the path, only one is marked.
Prep Interview questions
Implement a trie with insert, search, and startsWith. What separates the last two?
Design search with '.' wildcards (matches any one character).
How does longest-prefix match work, and why do routers use tries for it?
Your trie of 100k lowercase words uses gigabytes. Diagnose and fix.
Word Search II: find all dictionary words in a letter grid. Why is a trie the key optimization?
Watch out Common bugs
Storing 'application' creates a path through 'app' — but 'app' is only a word if some node is explicitly flagged. Treating any reachable node as a match makes every prefix of every key a false positive; search must check isEnd, startsWith must not.
An array-of-26 per node is fast but allocates 26 pointers even for chains where each node has one child — sparse datasets waste over 90% of slots. Use a map per node, or a compressed radix trie, once memory is measured and matters.
Indexing children by ch - 'a' crashes or corrupts on uppercase, accents, or emoji. Normalize input up front (case-fold, NFC normalization) and choose the alphabet deliberately — bytes, code points, or a validated character class.
Just clearing isEnd leaks the now-useless chain of nodes; but pruning must stop at any node that is still a word end or still has other children, or deleting 'app' destroys 'application'. Unwind from the leaf, removing only childless non-terminal nodes.
One screen Cheat sheet
The key IS the path: one tree edge per character, a flag marks where real words end.
- Lookup cost scales with key length, not collection size.
- isEnd flag distinguishes a stored word from a mere prefix — the #1 bug source.
- Prefix queries and longest-prefix match are single walks; hash tables can't do either cheaply.
- Child storage trade-off: fixed arrays (fast, fat) vs maps (lean, slower) vs radix compression.
- Normalize case/Unicode before indexing children.
- Delete = clear the flag, then prune childless non-terminal nodes upward — carefully.