Part 1 · Concepts · Trees
Trie (prefix tree)
A tree of characters where each path from the root spells a word. Finds words and prefixes in O(length of word).
How it works
Each node has a map from character to child, plus a flag for 'a word ends here'. Insert walks or creates one node per character. Search walks and checks the end flag. startsWith just checks the path exists. Autocomplete walks to the prefix node, then DFS collects words below it.
| insert / search / startsWith | O(L), L = word length |
| autocomplete | O(L + size of results) |
| space | O(total characters), can be large |
Reach for it when
- Autocomplete and type-ahead
- Prefix matching
- Word games and dictionaries
- Many lookups against a fixed set of strings
Implementation (JavaScript, tested)
class Trie {
root = { kids: new Map(), end: false };
insert(word) {
let n = this.root;
for (const c of word) {
if (!n.kids.has(c)) n.kids.set(c, { kids: new Map(), end: false });
n = n.kids.get(c);
}
n.end = true;
}
walk(s) {
let n = this.root;
for (const c of s) {
n = n.kids.get(c);
if (!n) return null;
}
return n;
}
search(word) {
return this.walk(word)?.end === true;
}
startsWith(prefix) {
return this.walk(prefix) !== null;
}
autocomplete(prefix, limit = 5) {
const start = this.walk(prefix),
out = [];
const dfs = (n, path) => {
if (out.length >= limit) return;
if (n.end) out.push(path);
for (const c of [...n.kids.keys()].sort()) dfs(n.kids.get(c), path + c);
};
if (start) dfs(start, prefix);
return out;
}
}Traps
- Forgetting the end flag: 'ca' is a prefix, not a word.
- Memory heavy. For a few lookups, a Set plus startsWith is simpler.
In real systems: HTTP routers (Fastify's find-my-way uses a radix tree, a compressed trie), IP routing tables, search box suggestions.
Say out loud: Lookups cost the word length, not the dictionary size, which is why routers and autocomplete use tries.