Tries
Tries (Prefix Trees)
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")) // trueisWord is what separates "ca" from "car". Without it every prefix would count as a word.
Autocomplete
Collecting everything below a prefix
javascript
function suggest(trie, prefix, limit = 10) {
const node = trie.findNode(prefix) // expose #find for this
if (!node) return []
const out = []
function walk(node, current) {
if (out.length >= limit) return
if (node.isWord) out.push(current)
for (const [ch, child] of node.children) {
walk(child, current + ch)
}
}
walk(node, prefix)
return out
}
console.log("suggest(root, \"ca\") returns every stored word starting with ca")The costs
- Insert and search - O(length of the word). Independent of how many words are stored.
- Prefix search - O(length of prefix), then O(matches) to collect.
- Space - one node per character in the worst case. This is the real cost.
A Set gives O(1) exact lookup and uses far less memory. A trie only pays for itself when prefixes matter.
Use it, or do not
- Use - autocomplete, spell check, IP routing, word games where you prune by prefix.
- Do not - exact membership only. A Set is smaller and faster.
- Do not - a few hundred words. Filtering an array is simpler and quick enough.
What a trie buys over a hash set
A Set answers "is this exact word present" in O(1) and cannot answer anything about prefixes. A trie answers "which words start with this" in time proportional to the prefix length, independent of how many words are stored - which is the entire reason autocomplete uses one.
Insert, search, and prefix search
javascript
class TrieNode {
constructor() {
this.children = new Map()
this.isWord = false
}
}
class Trie {
constructor() { this.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
}
#walk(prefix) {
let node = this.root
for (const ch of prefix) {
node = node.children.get(ch)
if (!node) return null
}
return node
}
has(word) {
const node = this.#walk(word)
return Boolean(node && node.isWord)
}
startsWith(prefix) {
return this.#walk(prefix) !== null
}
wordsWithPrefix(prefix) {
const node = this.#walk(prefix)
const out = []
if (!node) return out
;(function collect(current, built) {
if (current.isWord) out.push(prefix + built)
for (const [ch, child] of current.children) collect(child, built + ch)
})(node, "")
return out
}
}
const trie = new Trie()
for (const w of ["car", "card", "care", "dog"]) trie.insert(w)
console.log(trie.wordsWithPrefix("car")) // ["car", "card", "care"]The cost
Memory. Every node carries a map of children, so a trie over a large dictionary uses considerably more space than the strings themselves. Use one when prefix queries are the point; use a Set when they are not.