How to implement a Trie in JavaScript

Here is one reference implementation for a Trie (prefix tree) in JavaScript:

TrieTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
function Trie(letter = '') {
this.value = letter;
this.children = {};
this.isWord = false;
}
Trie.prototype.add = function(word, node = this) {
for (const letter of word) {
if (node.children[letter]) {
node = node.children[letter];
} else {
const newNode = new Trie(letter);
node.children[letter] = newNode;
node = newNode;
}
}
node.isWord = true;
};
Trie.prototype.find = function(word, node = this) {
let value = ''
for (const letter of word) {
if (node.children[letter]) {
node = node.children[letter];
value += letter;
}
}
return value === word ? node : null;
};
Trie.prototype.remove = function(word = '', node = this) {
if (!word) return null;
const chain = [];
// traverse down trie
for (const letter of word) {
if (node.children[letter]) {
chain.push(node) // we want all nodes accessible in chain so we can move backwards and remove dangling nodes
node = node.children[letter]
} else {
return null; // word is not in trie
}
}
if (Object.keys(node.children).length) { // if any children, we should only change isWord flag
node.isWord = false;
return node;
}
// Zero children in node.
// continue until we hit a breaking condition
let child = chain.length ? chain.pop() : null; // whatever node was
let parent = chain.length ? chain.pop() : null; // if node has parent
while (true) {
child && parent && delete parent.children[child.value]; // remove child;
if (Object.keys(parent.children).length || !chain.length) { // if more children or chain is empty, we're done!
node.isWord = false;
return node;
}
// otherwise, we have no more children for our parent and we should keep deleting nodes
// our next parent is what we pop from the chain
// our child is what our parent was.
child = parent;
parent = chain.pop()
}
};
Trie.prototype.findWords = function(value = '', node = this.find(value), words = []) {
Object.values(node.children).forEach((child) => {
if (child.isWord) words.push(value + child.value);
child.findWords(value + child.value, child, words);
});
return words;
};
Trie.prototype.hasWord = function(word) {
const node = this.find(word);
return !!node && node.isWord;
};

Test cases can be found at REPL.it