A trie in JavaScript: word lookup, prefix search and fuzzy matching on a real word list

A JavaScript Set tells you whether an exact word is in your list. It cannot tell you which words start with spel, or which are one typo away, without checking candidates one by one. A trie, or prefix tree, answers all three from one structure.
What a trie is
A trie stores strings letter by letter in a tree. The root stands for the empty string; each edge adds one letter; and the path from the root to any node spells a prefix. A flag on the node says whether that prefix is also a complete word. In the illustration above, car, card, care and cart all walk through the same C, A and R nodes, and only their last letters get nodes of their own.
The NIST Dictionary of Algorithms and Data Structures defines it as "a tree for storing strings in which there is one node for every common prefix". It also records the history: René de la Briandais described the idea in a 1959 paper on file searching with variable-length keys, and Edward Fredkin named it in "Trie Memory" in 1960. The name comes from retrieval and, by Fredkin's account, is pronounced "tree"; many programmers say "try" to tell it apart.
A trie in about forty lines
Each node holds a Map from a letter to a child node and a boolean end. Inserting a word walks down the tree and creates the nodes that are missing; looking it up walks down and checks the flag at the end.
class Trie {
constructor() {
this.root = { children: new Map(), end: false };
this.size = 0;
}
insert(word) {
let node = this.root;
for (const ch of word) {
let next = node.children.get(ch);
if (!next) {
next = { children: new Map(), end: false };
node.children.set(ch, next);
}
node = next;
}
if (!node.end) { node.end = true; this.size++; }
}
find(prefix) { // the node for a prefix, or null
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.find(word);
return node !== null && node.end;
}
hasPrefix(prefix) {
return this.find(prefix) !== null;
}
}
for...of iterates over code points rather than UTF-16 units, so an accented letter counts as one step. A lookup costs one step per letter whatever the size of the list: xylophone takes nine. A hash set is just as fast for exact lookups, so speed is not the reason to choose a trie; the prefix questions are.
Prefix search and autocomplete
hasPrefix is useful on its own: a solver for Boggle-style grids or anagrams can abandon a branch as soon as its prefix leads nowhere, since no English word starts with xq.
Autocomplete adds a depth-first walk below the prefix node. Visiting the children in alphabetical order returns the completions in dictionary order, and a limit stops the walk early:
complete(prefix, limit = 10) {
const start = this.find(prefix);
const out = [];
if (!start) return out;
const walk = (node, path) => {
if (out.length >= limit) return;
if (node.end) out.push(path);
for (const ch of [...node.children.keys()].sort()) {
walk(node.children.get(ch), path + ch);
}
};
walk(start, prefix);
return out;
}
trie.complete('xyl');
// ["xylem", "xylophone", "xylophones", "xylophonist", "xylophonists"]
A real search box wants the most likely words, not the first ones alphabetically, so it stores a weight with each word and often keeps the best weight of each subtree in its node to skip weak branches. Only the order of the walk changes.
Fuzzy matching: edit distance along the branches
The most interesting use for a spell checker is finding words within a given edit distance of a misspelling. The naive method computes the distance between the misspelling and every word in the list. Our step-by-step guide to Levenshtein distance builds that distance one row of a table at a time, and the trick, popularised by Steve Hanov in a blog post, is to notice that one row of the table corresponds to one prefix. Words that share a prefix share its rows, so each row is computed once per trie node instead of once per word.
function fuzzy(trie, word, maxCost) {
const results = [];
const firstRow = Array.from({ length: word.length + 1 }, (_, i) => i);
function visit(node, ch, prevRow, path) {
const row = [prevRow[0] + 1];
for (let i = 1; i <= word.length; i++) {
const cost = word[i - 1] === ch ? 0 : 1;
row.push(Math.min(row[i - 1] + 1, prevRow[i] + 1,
prevRow[i - 1] + cost));
}
const dist = row[word.length];
if (node.end && dist <= maxCost) results.push([path, dist]);
if (Math.min(...row) <= maxCost) { // can this branch still match?
for (const [c, child] of node.children) visit(child, c, row, path + c);
}
}
for (const [c, child] of trie.root.children) visit(child, c, firstRow, c);
return results.sort((a, b) => a[1] - b[1] || a[0].localeCompare(b[0]));
}
fuzzy(trie, 'speling', 1);
// [["spelling", 1], ["spewing", 1], ["spieling", 1]]
The work is done by the test on Math.min(...row): if every cell already exceeds the allowed distance, no word below this node can come back under it, so the whole branch is skipped. On our word list (below), the search for speling at distance 1 visits 874 of the trie's 141,570 nodes; the search for recieve at distance 2 visits 7,904, under 6% of them.
That second search also shows a limit of plain Levenshtein distance. At distance 1, the only match for recieve is relieve; the intended receive only appears at distance 2, as one of 13 matches, because swapping two letters counts as two edits. Likewise wrod at distance 1 gives prod, rod, trod and wood, but not word. The Damerau variant in the Levenshtein guide counts a swap as one edit, and it fits here too by keeping one more row. Ranking the candidates is a separate problem, covered in how spell checkers work.
What it costs on a real list
For real numbers, we loaded the lower-case entries of the American English list used by the Letterbench spell checker, the same SCOWL-based list as in our article on word ladders:
| Measure | Value |
|---|---|
| Words | 61,794 |
| Letters in all the words | 512,470 |
| Trie nodes (root included) | 141,570 |
| Nodes with no children (leaves) | 42,431 |
| Nodes after merging identical subtrees | 22,549 |
| Words starting with un | 1,288 |
Shared prefixes cut the letters to store from about 8.3 per word to about 2.3 nodes per word. But each node here is a JavaScript object with its own Map, far heavier than one character in a string, so this trie takes much more memory than the text file. You pay for the prefix and fuzzy queries; for plain membership a Set is smaller and simpler.
Making it smaller
Two refinements address the size problem, and either can be stored in flat typed arrays instead of objects to remove most of the per-node overhead:
- Compact (radix) tries merge chains of single-child nodes into one edge labelled with several letters. The NIST dictionary lists Patricia trees and compact tries among its specialisations. In our list, the five letters o-p-h-o-n that follow xyl in xylophone and xylophonist become one edge, because no word branches off inside them.
- Shared suffixes. A trie shares beginnings but repeats endings: -ing, -ed and -s are stored thousands of times. Merging identical subtrees turns the tree into a graph, known as a DAWG (directed acyclic word graph) or minimal acyclic automaton. On our list, that took the count from 141,570 nodes to 22,549, a reduction of about 84%, with exactly the same answers to lookups and prefix questions. Daciuk, Mihov, Watson and Watson described how to build the minimal automaton incrementally from a sorted word list, without building the full trie first.
The price of the graph is that an end node is shared by many words, so you cannot hang a weight on each word as easily: weighted autocomplete tends to keep a compact trie, while word games that only need yes or no favour the graph.
When to reach for a trie
Use one for prefix questions: completions, pruning in a word-game solver, edit-distance search. For errors of sound rather than typing, a phonetic key, as in our Soundex guide, is the better tool.
A trie earns its memory when the question starts with "which words begin with…"; for "is this a word?", a set is enough.
Sources
- Paul E. Black (ed.), Dictionary of Algorithms and Data Structures, NIST, trie (definition, pronunciation note and references to de la Briandais 1959 and Fredkin 1960).
- Jan Daciuk, Stoyan Mihov, Bruce W. Watson and Richard E. Watson, Incremental construction of minimal acyclic finite state automata, Computational Linguistics 26(1), 2000.
- Word list: SCOWL, as shipped with the Letterbench spell checker (American English, lower-case entries only). Node counts, leaves, merged-subtree count and visited-node counts computed on 14 November 2026 with the code on this page.
Under the hoodLevenshtein distance in JavaScript
Edit distance step by step, with the Damerau transposition variant.
Under the hoodHow spell checkers work
Word lists, affix rules, edit distance and how suggestions get ranked.
Words & word gamesWord ladders
HEAD to TAIL in five steps: Carroll's rules, solving tactics, and the shortest ladders our own word list allows.