Medium difficulty · Algorithm · Topics: tree, trie, string, design
A trie (prefix tree, from retrieval) stores a set of strings by sharing their common prefixes: each edge is one character, and a path from the root spells a prefix. Looking up a word or asking "does any word start with this prefix?" costs time proportional to the length of the string, not to how many words are stored. Tries power autocomplete, spell checkers, IP routing tables and word games. This sample implements insert, search, startsWith and delete.
Think of a paper dictionary's thumb tabs taken all the way: pick the tab for the first letter, then a sub-tab for the second, and so on. Words that start the same way share the same tabs, so "car", "cart" and "cat" share the path c → a.
Each node stores:
children: a map from the next character to the child node,isEnd: whether a stored word ends exactly here,letter and val: the character on the edge into the node and the label drawn for it (t, or t• when a word ends there). The trie logic never reads them; they only make the picture readable.isEnd is what tells a stored word ("car") apart from a mere prefix of a longer word ("ca").
setEnd(true).s from the root; return the node reached, or null as soon as an edge is missing.walk(word) must succeed and land on a node with isEnd.walk(prefix) only has to succeed.setEnd(false) (return false if it was not set). On the way back up, delete a child edge when that child is no longer the end of a word and has no children left, so no dead branches remain.Case 0 inserts car, cat, cart, dog, runs a few queries, and deletes cat. • marks isEnd, as in the node labels.
insert "car" root -> c -> a -> r• (3 new nodes)
insert "cat" reuse c, a; new t under a a has children {r, t}
insert "cart" reuse c, a, r; new t under r
insert "dog" new branch d -> o -> g•
root
├─ c
│ └─ a
│ ├─ r•
│ │ └─ t• "cart"
│ └─ t• "cat"
└─ d
└─ o
└─ g• "dog"
search "cat" c, a, t reached, t is marked true
search "ca" c, a reached, a is not marked false
startsWith "ca" c, a reached true
delete "cat" depth 3: unmark t true
back at a: t is unmarked and childless -> delete a.children["t"]
back at c: a still has r -> keep
search "cat" a has no t edge false
startsWith "do" d, o reached true
| Operation | Time | Why |
|---|---|---|
| insert / search / startsWith | O(L) | one edge per character of the word or prefix (L = its length) |
| delete | O(L) | one recursive call per character, pruning on the way back |
| space | O(total characters stored) | at most one node per character; shared prefixes are stored once |
| space with array children | O(nodes · alphabet) | a fixed array of 26 slots per node is faster but wastes memory on sparse nodes |
startsWith, autocomplete, "all words with prefix p"), lexicographic order for free (visit children in sorted order), lookups independent of the number of stored words.search must also check isEnd, otherwise search("ca") returns true.isEnd.ch.charCodeAt(0) - 97) and then meeting uppercase letters, digits or Unicode: the index falls outside the array. A map, as here, accepts any character.this.root is drawn as a tree: every node shows its letter (the edges carry the same character), • marks the end of a word, and new nodes appear as insert creates them.node as it moves down one edge per character ch; in remove, depth points into word.• when setEnd(true) runs, and the t• branch under a disappear when delete("cat") prunes it.Input:
["Trie", "insert", "insert", "insert", "insert", "search", "search", "startsWith", "delete", "search", "startsWith"]
[[], ["car"], ["cat"], ["cart"], ["dog"], ["cat"], ["ca"], ["ca"], ["cat"], ["cat"], ["do"]]
Output:
[null, null, null, null, null, true, false, true, true, false, true]
0 <= word.length <= 2000; at most 3 * 10^4 operations.class Trie {
constructor() {
this.root = new TrieNode("");
}
insert(word) {
let node = this.root;
for (const ch of word) {
// Create the edge for ch the first time any word needs it
if (node.children[ch] === undefined) node.children[ch] = new TrieNode(ch);
node = node.children[ch];
}
node.setEnd(true);
}
search(word) {
const node = this.walk(word);
return node !== null && node.isEnd;
}
startsWith(prefix) {
return this.walk(prefix) !== null;
}
// Follows the characters of s from the root; null if the path breaks off
walk(s) {
let node = this.root;
for (const ch of s) {
node = node.children[ch];
if (node === undefined) return null;
}
return node;
}
delete(word) {
return this.remove(this.root, word, 0);
}
// Unmarks word below node, then prunes children that no longer lead to any word
remove(node, word, depth) {
if (depth === word.length) {
if (!node.isEnd) return false; // word was never stored
node.setEnd(false);
return true;
}
const ch = word[depth];
const child = node.children[ch];
if (child === undefined) return false;
const isRemoved = this.remove(child, word, depth + 1);
if (isRemoved && !child.isEnd && Object.keys(child.children).length === 0) {
delete node.children[ch];
}
return isRemoved;
}
}
// Declared after Trie: the runner constructs the first top-level class
class TrieNode {
constructor(letter) {
this.letter = letter; // character on the edge into this node ("" for the root)
this.children = {}; // letter -> TrieNode
this.setEnd(false);
}
// isEnd: a stored word ends here. val is only the label drawn on the node, e.g. "t" or "t•"
setEnd(isEnd) {
this.isEnd = isEnd;
this.val = (this.letter === "" ? "root" : this.letter) + (isEnd ? "•" : "");
}
}