new: 0
A prefix tree turns a dictionary into a character-by-character graph where every path from root to a marked node spells a word. Lookups stay O(L) in word length regardless of dictionary size, and prefix queries come for free — something a hash set can never give you.
A trie is a tree where the path from the root spells a string — so every word that shares a prefix shares the same nodes, and looking up a word is just walking that path letter by letter, costing O(L)no matter how many millions of words you've stored.
Picture a maze where every fork is labelled with a letter. Standing at the root, you spell your word one character at a time: the letter you're holding tells you which door to walk through. There's never a search — your own characters dictate the path. If the door you need isn't there, that prefix simply doesn't exist and you stop immediately.
Each node carries up to 26 children (one per letter) and a single isEndflag. The flag is the only thing that distinguishes “a real word ends here” from “this is just a place partway along a longer word.” The path being walkable proves a prefix; the isEnd flag proves a word.
Here is a trie holding {cat, car, card, dog}. Watch how cat, car, and card all reuse the single ca path — the • marks an isEnd node:
(root)
/ \
c d
| |
a o
/ \ |
t r g• "dog"
• |\
"cat" • d• "car", "card"
(car) (card)
The "ca" path is laid down once, then branches into t and r.
Storing "card" after "car" adds a single new node (d) — the
"car" prefix is reused, never copied. That sharing IS the trie.Now a search. You don't scan anything — you follow the path your characters spell, and the isEnd flag at the end decides the answer:
search("car"): start at (root)
'c' → child exists? yes → step to node c
'a' → child exists? yes → step to node ca
'r' → child exists? yes → step to node car
end of word → is this node isEnd? yes → TRUE
search("ca"): walk c → a, reach node "ca", but isEnd? NO → FALSE
(the PATH exists, but no word ends here)
search("cab"): walk c → a, then ask for child 'b' → missing → FALSEWhen a problem smells like a dictionary, climb these rungs in order — the structure picks itself:
isEnd = true (after the loop, never inside it).false. At the end, the answer is node.isEnd(for a full word) or just “you arrived” (for startsWith).'.' (or you want every word under a prefix), recurse into all children instead of one.The invariant to say out loud before you code: reaching a node only proves the prefix exists — only isEnd proves a complete word was inserted. Confuse the two and you get the single most common trie bug.
search walks then checks isEnd; startsWith walks and is happy just to arrive.”isEnd— that root is the shortest stored prefix.”search("ap") returns true when only "apple"was inserted, you checked “does the node exist” instead of “is this node isEnd.”Strip away the specific problem and a trie query is the same three moves: out of characters → forced step on a letter → branch on a wildcard. Read it as a sentence, not as code:
search(node, word, i): # i = how far into word we are
if i == word.length: # 1. consumed every character
return node.isEnd # a word ends here? only then TRUE
ch = word[i]
if ch is a real letter: # 2. one forced step
next = node.children[ch]
if next is missing: return False # dead prefix — stop
return search(next, word, i + 1)
if ch == '.': # 3. wildcard — try EVERY child
for child in node.children:
if search(child, word, i + 1):
return True
return FalseThe exact-search version is just rung 1 + rung 2 — drop the wildcard branch. The grid word-search version replaces “word[i]” with “the four neighbouring cells” and the trie node travels alongside the cursor. Same skeleton, different driver.
The payoff that makes a trie worth the nodes: every operation walks at most L nodes (the length of the query) and never looks at the rest of the trie. Add a million more words and a lookup costs exactly the same.
Each node represents one character position along a word. A node holds two things: a children map (or fixed-size array of 26 for lowercase-only input) pointing to the next character, and an isEnd flag that marks a complete word without ending the path (longer words can share the same prefix).
Words that share a prefix share nodes. Inserting "apple" and "app" lays down five nodes; "app" just sets isEnd at depth 3 instead of creating new nodes. Every operation — insert, search, startsWith — walks at most L nodes and never touches the rest of the trie.
O(L)exact membership checks but has no structural knowledge of prefixes. To ask "does any stored word start with 'ap'?" you must scan every word. A trie answers in O(2) — just walk two nodes.A trie of n words of average length L uses at most O(n × L) nodes in the worst case (no shared prefixes). In practice, shared prefixes make it far smaller. Choose your node structure based on the alphabet:
children: TrieNode[26]) — fastest index, but wastes memory on sparse branching and breaks for non-lowercase or Unicode input.children: Map<string, TrieNode>) — handles any character set, allocates only used children. Slightly higher constant per lookup, but correct for interview problems with mixed characters.For grid word-search, the trie doubles as a pruning structure: once a prefix no longer exists in the trie, you abort the DFS immediately — the classic reason tries beat brute force on Word Search II.
cat, car, can, dog into a trie. Walk down letter by letter, reusing nodes where prefixes match. One node per letter on the path.Reach for a trie when the problem is fundamentally about shared prefixes or repeated prefix lookups over a fixed dictionary. If the problem only needs exact membership for isolated words, a hash set is simpler.
| autocomplete / prefix search / startsWith | trie insert + startsWith walk |
| many words sharing prefixes | trie to compress shared paths |
| search words with '.' wildcards | trie + DFS branching on wildcard nodes |
| find all dictionary words in a grid | build trie of words, DFS the grid pruning by trie |
| implement a dictionary with prefix queries | trie with isEnd flag |
| stream of words + repeated prefix lookups | insert once, query O(L) repeatedly |
O(L) lookup with far less code — a trie adds complexity for zero benefit.Map-based trie still works, but memory per node climbs fast. Verify the input constraints before assuming lowercase letters only.When → Every trie problem starts here. Use a Map for children unless the problem guarantees lowercase letters only and you want the micro-opt of a fixed array.
class TrieNode {
children: Map<string, TrieNode> = new Map();
isEnd = false; // marks a complete word boundary
}
class Trie {
private root = new TrieNode();
/** O(L) — one node per character, shared with all prior inserts */
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.isEnd = true; // mark end AFTER the last char
}
}isEnd after the loop, not inside it → setting it inside would mark every intermediate prefix as a complete word, silently breaking search().When → The core read operations. Both share a private _walk helper; the only difference is whether you check isEnd at the destination node.
class Trie {
private root = new TrieNode(); // assume insert() already defined
/** O(L) — returns true only if the COMPLETE word was inserted */
search(word: string): boolean {
const node = this._walk(word);
return node !== null && node.isEnd; // must reach end AND be a full word
}
/** O(L) — returns true if any inserted word begins with prefix */
startsWith(prefix: string): boolean {
return this._walk(prefix) !== null; // reaching the node is enough
}
private _walk(s: string): TrieNode | null {
let node: TrieNode = this.root;
for (const ch of s) {
if (!node.children.has(ch)) return null;
node = node.children.get(ch)!;
}
return node;
}
}search('app') must return false when only 'apple' was inserted, even though the path exists. Walking to a node proves the prefix; only isEnd proves the word.When → Any character in the pattern can be a '.' that matches exactly one character. DFS branches on every child when it sees a dot. The same DFS skeleton also powers grid word-search when you walk the trie in lock-step with the board.
class WordDictionary {
private root = new TrieNode(); // assume TrieNode with Map children
addWord(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.isEnd = true;
}
/** '.' matches any single character — DFS branches on every child */
search(word: string): boolean {
return this._dfs(this.root, word, 0);
}
private _dfs(node: TrieNode, word: string, i: number): boolean {
if (i === word.length) return node.isEnd;
const ch = word[i];
if (ch !== '.') {
const next = node.children.get(ch);
return next !== undefined && this._dfs(next, word, i + 1);
}
// wildcard: try every child branch
for (const child of node.children.values()) {
if (this._dfs(child, word, i + 1)) return true;
}
return false;
}
}'.' fans out to all children at that depth. In the worst case (all dots) this is O(26^L), but real dictionaries prune the tree heavily. For Word Search II, extend this DFS to walk the grid simultaneously and delete matched words from the trie to avoid emitting duplicates.This is the #1 trie bug. If you only check whether a node exists, search('ap') returns true when only "apple" is stored. Always set isEnd = true on the final node during insert, and always check it in search().
A new Array(26) indexed by ch.charCodeAt(0) - 97 explodes with negative indices or out-of-bounds access the moment the input contains uppercase letters, digits, or spaces. Default to a Map unless the problem explicitly guarantees lowercase English letters only.
The grid DFS can reach the same trie node via multiple paths and emit the same word multiple times. The fix: after recording a found word, set node.isEnd = false (or delete the word from the trie) so subsequent DFS visits skip it. Collecting results into a Set is a band-aid — mutating the trie is the canonical solution.
Tries can hold a large number of nodes. With a fixed array of 26 per node and many short words with little prefix overlap, memory usage scales with the total characters inserted rather than unique prefixes. Profile constraints before committing to a trie over a hash set for exact-match-only problems.