Pattern Guide
Trie (Prefix Tree)
"Fast prefix lookup. One character per level."
A Trie is a tree where each path from root to a leaf represents a string. It gives O(L) lookup/insert/delete for strings of length L, regardless of how many strings are stored. Master the standard Trie, compressed Trie, and XOR Trie.
12 min readtrie problems →
Problems you can solve with this pattern
8 problems · click any to start solving
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
}
}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
}
}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).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