Lesson 22
Tries: Trees of Characters
The data structure behind autocomplete, spell-check and IP routing.
01Why it matters & the intuition
When keys are strings and you care about prefixes, a trie answers 'which words start with …?' in time proportional to the prefix length — independent of how many words are stored.
Think of it like…
A dictionary's thumb index, repeated at every letter: the 'c' tab leads to 'ca', 'ce', 'ch'… Words that share a prefix share a path, so 'car', 'cart' and 'care' reuse the nodes c → a → r.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- prefix path
- completions
03Key ideas
Node = map of children
Each node maps a character to a child node and stores a flag end marking that a complete word stops here.
Insert & search
Walk one character at a time, creating nodes on insert. Search succeeds if you reach the last character *and* end is true.
Prefix queries
startsWith only needs to reach the last prefix character. Collecting all completions is a DFS from that node.
Memory trade-off
Tries can use more memory than a hash set, but they share prefixes and support ordered and prefix queries a hash set cannot.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class TrieNode {
children = new Map<string, TrieNode>();
end = false;
}
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.end = true;
}
private walk(prefix: string): TrieNode | null {
let node: TrieNode | undefined = this.root;
for (const ch of prefix) {
node = node.children.get(ch);
if (!node) return null;
}
return node;
}
has(word: string) { return this.walk(word)?.end ?? false; }
startsWith(prefix: string) { return this.walk(prefix) !== null; }
complete(prefix: string): string[] {
const start = this.walk(prefix);
const out: string[] = [];
const dfs = (node: TrieNode, path: string) => {
if (node.end) out.push(path);
for (const [ch, child] of node.children) dfs(child, path + ch);
};
if (start) dfs(start, prefix);
return out;
}
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Insert word of length L | O(L) | — |
| Search / startsWith | O(L) | — |
| Space | — | O(total characters) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Longest common prefix
Write longest_common_prefix(words) returning the longest prefix shared by every string in the array (empty string if none or if the array is empty).