Anatomy of a trieCore idea
Inserting cat, car and dog: the first two share the c → a path. Each node also records whether a word ends there (marked ★).
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph TD
R(("root")) --> C["c"]
R --> D["d"]
C --> A["a"]
A --> T["t ★"]
A --> R2["r ★"]
D --> O["o"]
O --> G["g ★"]
class R grey
class C,A orange
class T,R2,G green
class D,O blue
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eThe insert / search / startsWith templatePattern
Almost every trie problem reuses this node: an array (or map) of children plus an end-of-word flag.
class TrieNode {
children: (TrieNode | undefined)[] = new Array(26);
isEnd = false;
}
class Trie {
private root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const ch of word) {
const idx = ch.charCodeAt(0) - 97;
if (!node.children[idx]) node.children[idx] = new TrieNode();
node = node.children[idx]!;
}
node.isEnd = true;
}
search(word: string): boolean {
const node = this.find(word);
return !!node && node.isEnd;
}
startsWith(prefix: string): boolean {
return !!this.find(prefix);
}
private find(key: string): TrieNode | undefined {
let node: TrieNode | undefined = this.root;
for (const ch of key) {
node = node.children[ch.charCodeAt(0) - 97];
if (!node) return undefined;
}
return node;
}
}Counts and collecting wordsPattern
Two upgrades make a trie interview-ready. A count field on each node tracks how many words pass through it, which lets you rank autocomplete suggestions. And a DFS from any node collects every word below it:
function collect(node: TrieNode, prefix: string, out: string[]): void {
if (node.isEnd) out.push(prefix);
for (let i = 0; i < 26; i++) {
const child = node.children[i];
if (child) collect(child, prefix + String.fromCharCode(97 + i), out);
}
}
// collect(root, "", words) returns every stored wordWhere tries are usedUses
Autocomplete
Walk to the prefix node, then DFS for the top K words by count.
Spell check
Insert the dictionary, then look up each word.
Word Search on a grid
Put all words in a trie and DFS the board, stopping any path that is not a prefix.
Longest common prefix
Walk down while there is exactly one child and no word ends.
IP routing
Network prefixes (CIDR) map naturally onto a binary trie.
Trie vs the alternativesCompare
| Structure | Exact lookup | Prefix query | Notes |
|---|---|---|---|
| Hash map | O(L) | Scan everything | Best for exact lookups only. |
| Sorted array + binary search | O(L log n) | Yes, with lower_bound | Great for a dictionary that never changes. |
| Trie | O(L) | O(L) | Best when prefixes matter. |
| Radix (compressed) trie | O(L) | O(L) | Merges single-child chains to save space; overkill for interviews. |
Common mistakesPitfalls
Frequently asked questionsFAQ
How does a trie make autocomplete fast?
Autocomplete only needs to reach the node for the typed prefix (O(L)) and then DFS its subtree for the top suggestions by count. A hash map would have to scan every stored word to check each one startsWith the prefix, which is O(N*L).
Can a trie handle numbers or unicode?
Yes. Replace the fixed 26-slot child array with a map or a larger alphabet bucket and the same structure works for any symbol set. Binary tries are the simplest case, with children 0 and 1, which is how IP routing tables and several bit-manipulation problems end up modeled as tries.
Is a trie better than a set for exact membership?
Not for a single lookup: a hash set gives expected O(1) membership with far less code. A trie earns its keep when you need prefix queries, wildcard or dot-separated matching, or a deterministic serialized traversal. Its space cost is competitive only when many stored strings share long prefixes.
Now explain tries to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.