Pattern Reference
Trie
"Prefix tree for dictionary, autocomplete, spell check, IP routing, XOR max pair."
Loading...
Deep Dive Tutorial
A Trie stores strings by their characters, one character per level. Each node can have up to 26 children (for lowercase English). Tries answer prefix queries in O(L) time where L is the string length — independent of how many strings are stored. This makes them ideal for autocomplete, spell check, and problems involving common prefixes.
Standard Trie Implementation
Trie with insert, search, and startsWith
class TrieNode {
constructor() {
this.children = {}; // or new Array(26).fill(null)
this.isEnd = false;
}
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) node.children[ch] = new TrieNode();
node = node.children[ch];
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return node.isEnd; // must reach a word-ending node
}
startsWith(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return true; // just need the prefix path to exist
}
}lightbulb
search vs startsWith: Both traverse the trie character by character. The only difference is the final check:
search requires node.isEnd === true (the string itself was inserted), while startsWith just needs the path to exist (any word with that prefix was inserted).Worked Problems
More Worked Problems
Even More Worked Problems
brain
Trie vs HashMap decision:
- Need prefix search / autocomplete → Trie wins (HashMap can't query prefixes)
- Need exact word lookup only → HashMap is simpler and faster
- Need maximum XOR of two numbers → Binary Trie (insert bits)
- Wildcard/regex matching on words → Trie with DFS on wildcards
- Multiple word search in grid → Build Trie, DFS on grid with pruning
- Replace with shortest prefix → Trie insert roots, walk and stop at first end marker
- Need prefix search / autocomplete → Trie wins (HashMap can't query prefixes)
- Need exact word lookup only → HashMap is simpler and faster
- Need maximum XOR of two numbers → Binary Trie (insert bits)
- Wildcard/regex matching on words → Trie with DFS on wildcards
- Multiple word search in grid → Build Trie, DFS on grid with pruning
- Replace with shortest prefix → Trie insert roots, walk and stop at first end marker