Trie Implementation in JavaScript
A trie (prefix tree) supports insert, exact-match search, and prefix-search in O(L) where L is the word length, regardless of how many words are stored. This makes it the right structure for autocomplete, spell-check, and IP-routing tables. This snippet covers a Map-backed trie with insert and search, the startsWith prefix scan that powers autocomplete, and a wordsWithPrefix collector that returns every match.
769 views
14
class Trie {
constructor() {
this.root = { children: new Map(), end: false };
}
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false });
node = node.children.get(ch);
}
node.end = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return node.end;
}
}
const t = new Trie();
for (const w of ['cat', 'car', 'cart']) t.insert(w);
console.log(t.search('cat')); // true
console.log(t.search('ca')); // false (prefix, not full word)
console.log(t.search('cars')); // falseEach trie node stores a Map of next-character pointers and a boolean end flag marking whether a word terminates there. Insert walks the chain creating nodes as needed, then sets end = true at the last character. Search walks the same chain and returns node.end, which is what distinguishes 'this is a stored word' from 'this is just a prefix'. The Map (not a plain object) keeps the API clean for unicode keys and avoids prototype-pollution gotchas. Time complexity is O(L) per operation, space is O(N * L) total for N words.
Trie.prototype.startsWith = function(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return true;
};
const t2 = new Trie();
for (const w of ['code', 'coder', 'cream', 'cup']) t2.insert(w);
console.log(t2.startsWith('co')); // true
console.log(t2.startsWith('cre')); // true
console.log(t2.startsWith('cz')); // falsestartsWith is identical to search minus the final end check: both walk the trie, but startsWith returns true the moment the prefix is fully consumed. This is the operation behind autocomplete suggestions, command palettes, and any 'show me everything starting with X' feature. The shape stays O(L) per query, which is asymptotically better than a hash-table-of-strings approach because it does not need to scan every stored word.
Trie.prototype.wordsWithPrefix = function(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.children.has(ch)) return [];
node = node.children.get(ch);
}
const out = [];
function collect(n, current) {
if (n.end) out.push(current);
for (const [ch, child] of n.children) collect(child, current + ch);
}
collect(node, prefix);
return out;
};
const t3 = new Trie();
for (const w of ['cat', 'car', 'cart', 'cats', 'dog']) t3.insert(w);
console.log(t3.wordsWithPrefix('ca').sort()); // ['car', 'cart', 'cat', 'cats']
console.log(t3.wordsWithPrefix('zz')); // []The collector first walks down to the prefix subtree, then runs a DFS of the subtree to collect every word ending under it. This is exactly the back end of a real autocomplete: 'show me all words starting with what the user has typed'. The recursive walk is O(K * L) where K is the number of matches and L is the average word length, which is the optimal output size. Pruning the subtree at the top of the function is what makes the prefix lookup itself constant-time relative to the dictionary size.