Build a prefix tree where each node holds a map of child characters and an isEnd flag — then insert, search, and startsWith all reduce to walking that path one character at a time.
Implement a Trie with three methods. insert(word) stores a word; search(word) returns true only if the exact word was inserted; startsWith(prefix) returns true if any stored word begins with that prefix. After insert("apple"): search("apple")→true, search("app")→false, startsWith("app")→true. Then insert("app") makes search("app")→true.
children map from a character to the next node. Shared prefixes share nodes, so "app" and "apple" reuse the same first three nodes. The single extra bit per node — isEnd — is what distinguishes a stored word from a mere prefix. That one flag is the entire difference between search and startsWith.TrieNode has children: Record<string, TrieNode> and a boolean isEnd, because we must both branch by character and record where words terminate.isEnd = true — that is what makes it a real word and not just a passed-through prefix.null (the path fell off the tree); otherwise descend. Return the node you land on. Both reads use this.node.isEnd (a complete word), while startsWith is happy with any surviving path. Same walk, different finish line.search("app") returns false even after insert("apple"), because the node at "app" exists but its isEnd is still false. Forgetting the isEnd check makes search behave like startsWith — a very common bug.Every operation costs O(L) in the length of the key — not the number of stored words — which is exactly why prefix queries are fast. Space is O(total characters) across all inserted words, shared along common prefixes. A plain hash set answers exact search in O(L) too, but cannot answer startsWith without scanning everything.
. wildcard branches into all children), Design Add/Search Words Data Structure, and autocomplete / longest-common-prefix problems.root node with no children. Run each operation in order.class TrieNode {
children: Record<string, TrieNode> = {};
isEnd = false;
}
class Trie {
private root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const c of word) { // walk, creating as we go
if (!node.children[c]) node.children[c] = new TrieNode();
node = node.children[c];
}
node.isEnd = true; // mark the terminal node
}
search(word: string): boolean {
const node = this.walk(word);
return node !== null && node.isEnd; // full word ⇒ must be a terminal
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== null; // any path is enough
}
// Walk the path for s; return the node it ends at, or null if it falls off.
private walk(s: string): TrieNode | null {
let node = this.root;
for (const c of s) {
if (!node.children[c]) return null;
node = node.children[c];
}
return node;
}
}TrieNode is just a children map (char → node) plus an isEnd boolean. No character is stored in the node — the character is the edge(the key in the parent's map).isEnd = true there.null. Otherwise return the final node.isEnd true. The isEnd check is what stops a prefix from counting as a word.isEnd. If the path exists, some word goes through it.O(L) in the key length L. Total space is O(Σ word lengths), shared across common prefixes (worst case if no prefixes are shared).TrieNode[26] array indexed by c - 'a' for less overhead per node.isEnd, then prune nodes bottom-up while they have no children and aren't themselves a word.., recurse into every child (this is LC 211).isEnd below it.| prefix / startsWith / autocomplete | trie (prefix tree) |
| distinguish full word from prefix | isEnd flag on the node |
| dictionary pruning a grid DFS | trie of words (Word Search II) |
| "." wildcard in search | recurse into all children |
class TrieNode {
children: Record<string, TrieNode> = {};
isEnd = false;
}
class Trie {
root = new TrieNode();
insert(w: string) {
let n = this.root;
for (const c of w) n = (n.children[c] ??= new TrieNode());
n.isEnd = true;
}
private walk(s: string) {
let n = this.root;
for (const c of s) { if (!n.children[c]) return null; n = n.children[c]; }
return n;
}
search(w: string) { const n = this.walk(w); return !!n && n.isEnd; }
startsWith(p: string) { return this.walk(p) !== null; }
}children map (char → TrieNode) and an isEnd boolean. The character lives on the edge, not in the node.