Tries
Tries (Prefix Trees)
Written by Swapnil RajaPublished
A trie answers one question a hash map cannot: which words start with this? That is the whole reason it exists, and if you do not need prefixes you do not need a trie.
The structure
Each node is one character. Words that share a prefix share the path to it, so "car", "card" and "care" all pass through the same c-a-r nodes.
A trie
javascript
class TrieNode {
children = new Map()
isWord = false
}
class Trie {
#root = new TrieNode()
insert(word) {
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.isWord = true
}
has(word) {
const node = this.#find(word)
return node !== null && node.isWord
}
// The method a Set cannot offer.
startsWith(prefix) {
return this.#find(prefix) !== null
}
#find(prefix) {
let node = this.#root
for (const ch of prefix) {
if (!node.children.has(ch)) return null
node = node.children.get(ch)
}
return node
}
}
const trie = new Trie()
for (const w of ["car", "card", "care", "dog"]) trie.insert(w)
console.log(trie.has("car")) // true
console.log(trie.has("ca")) // false — a prefix, not a word
console.log(trie.startsWith("ca")) // true