What is a trie?
A trie (pronounced "try", also called a prefix tree) is a tree that stores words letter by letter — one node per character — so words that start the same way share the same path. From the root, the path
c → a is walked by every word starting with ca; from that shared node the letter t completes cat, while r branches onward toward car, care, and card. Each node where a real word ends carries a flag saying so.In this lesson you'll learn how words are inserted and found by walking letter paths, why shared prefixes make lookups independent of dictionary size, and how a trie powers autocomplete.
Where it matters: you're building a search box. The user types
ca and you must instantly suggest every matching word — cat, car, care, card — on every keystroke, over a dictionary of hundreds of thousands of words. Checking every stored word for the prefix re-examines the shared letters of cat, car, care over and over. In a trie, every word beginning ca lives under the same c → a path — so looking up a prefix is just walking its letters, no matter how many words are stored.Build one in words with three words. Store SUN: the letters S → U → N, one node each, with a dot marking "a word ends here". Store SEA: the S already exists — reuse it! — so only E and A are new. Store SET: S and E both exist, so one new letter T does the whole job. Now type
SE in the search box: walk S → E — two hops — and SEA and SET light up below it, while SUN's branch is never even visited. Watch it grow below. (The coded insert/search and autocomplete live in the See it step.)This section has a step-by-step animation in the interactive lesson.
Quick check
Searching a trie for a word of length L costs O(L). It does NOT depend on…
Answer it in the interactive lesson to keep your progress.
The core operations
Each node is a map from a letter to a child node, plus an
isEnd flag marking a real word-end. Two moves cover it:- insert(word) — walk the letters from the root, creating child nodes as needed, then mark the final node
isEnd. - search(word) — walk the letters; if any is missing the word isn't there, otherwise check the final node's
isEnd.
(A prefix search is the same walk but, instead of checking
isEnd, it gathers every word-end in the subtree below.) Here are both, inserting cat:Insert and Search in JavaScript
const root = {};
function insert(word) {
let node = root;
for (const ch of word) {
if (!node[ch]) node[ch] = {};
node = node[ch];
}
node.isEnd = true;
}
function search(word) {
let node = root;
for (const ch of word) {
if (!node[ch]) return false;
node = node[ch];
}
return node.isEnd === true;
}
insert('cat');
console.log(root); // { c: { a: { t: { isEnd: true } } } }Quick check
You insert only "card". Predict what search("car") returns.
Answer it in the interactive lesson to keep your progress.
Your first trie problem: autocomplete
Given what the user has typed so far (
ca), suggest every stored word that starts with it. A trie makes this cheap: walk the typed letters, then gather every word-ending below.The steps
- Start at the root and walk one node per typed letter (
c → a). If a letter is missing, there are no matches. - From the node you land on, collect every word-end (
isEnd) in the subtree below — those are the completions. - (Exact search is the same walk; you just check
isEndon the final node instead of gathering.)
Prefix-sharing pays off immediately: inserting
car after cat creates only the new r, because c → a already exist. Then autocomplete ca: walk c → a, collect below → cat, car. Only the letters you typed were ever examined. (The See it step animates both — the shared-path insert and the autocomplete gather.) The prefix walk, then a small recursive gather.Autocomplete in JavaScript
insert('car'); // reuses c → a from 'cat', adds only r
function autocomplete(prefix) {
let node = root;
for (const ch of prefix) {
if (!node[ch]) return []; // nothing starts with this
node = node[ch];
}
const words = [];
(function gather(n, sofar) {
if (n.isEnd) words.push(sofar);
for (const ch of Object.keys(n)) {
if (ch !== 'isEnd') gather(n[ch], sofar + ch);
}
})(node, prefix);
return words;
}
console.log(autocomplete('ca')); // ['cat', 'car']
console.log(search('can')); // false — no node for 'n' after 'ca'Quick check
Trie holds cat, car, card, dog. Predict what autocomplete("ca") returns and what it never touches.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Forgetting the end-of-word flag. Without
isEnd, you cannot tell a stored word from a mere prefix —carwould look present just becausecardis. Mark true word-ends. - Memory cost. A node per character across many words uses real memory; if you only ever need exact lookups (no prefixes), a hash set is simpler and lighter.
- Case and character set. Decide upfront whether keys are lowercased, and how you map characters to children (object vs. fixed array).
Quick check
'ca' has a node in a trie containing 'cat'. Is 'ca' a stored word?
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, the whole point is that cost tracks the query length, not the dictionary size:
| Operation | Trie | Hash set of words |
|---|---|---|
| exact search | O(L) | O(L) average |
| insert | O(L) | O(L) average |
| all words with a prefix | O(L + matches) | O(N·L) — scan everything |
Space is
O(total characters), but shared prefixes reduce it — cat/car/care share the ca path once. The prefix row is the trie's whole reason to exist.Key takeaways:
- A trie is a prefix tree: one node per character, common prefixes shared.
- Lookups are
O(L), independent of word count — its edge over a hash set for prefix queries. - The
isEndflag is what separates a real word from a mere prefix.
This answers prefix questions in time proportional to the prefix. The See it step animates the two core scenes: insert & search (watch a second word reuse the shared letters) and autocomplete (walk the prefix, gather the subtree). These classics each get their own lesson later (no need to know them yet): word search II (a trie prunes a grid DFS hard) and replace words / longest common prefix. Next up in order: Backtracking — building every possibility by choosing, exploring, and undoing.