What a trie is
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 word for the prefix is O(N·L) per keystroke, and it re-examines the shared letters of cat, car, care over and over.A trie (prefix tree) stores words by their letters, 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 real word-ending is flagged). Every word beginning ca lives under the same c → a path. Looking up a prefix is just walking those letters — O(L) in the prefix length, independent of how many words the trie holds.In the animation, watch what happens when a second word sharing a prefix is inserted: the walk reuses the existing letter nodes and only creates the letters that differ. That reuse is the entire data structure.
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: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.)
First, watch prefix-sharing pay off — insert
car, and only the new r is created since c → a already exist. Then autocomplete ca: walk c → a, collect below → cat, car. Only the letters you typed were ever examined. In JavaScript (search confirms exact words too):This section has a step-by-step animation in the interactive lesson.
insert('car');
console.log(search('car')); // true
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. These classics each get their own lesson later (no need to know them yet): autocomplete & typeahead, 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.