level 6 · Trees
Trie (Prefix Tree)
Words that start the same share the same path — so autocomplete is free.
what is it
Start here
A trie doesn't store words. It stores **paths**. Each edge is a letter, and spelling out the letters from the root down to a node gives you a word — or the beginning of one.
That means two words starting the same way physically share the same nodes. 'car' and 'card' overlap for three letters and only then does 'card' branch off with a d. Nothing is duplicated. The structure's *shape* is the prefix relationship.
Notice that a node doesn't contain its word anywhere. The word is the journey, not the destination — which is why a node needs a flag (the double ring) just to say 'yes, a word ends here'.
Now the payoff, and it's genuinely lovely. Find every word starting with 'ca'. In a list of a million strings you'd check all million. In a trie you walk **two letters** — and then simply stop. Everything hanging below that node is an answer. You didn't search for them. You didn't compare anything. They were just *there*, sitting under the path.
That's why the search box suggests things the instant you type. It isn't searching. It's standing at a node.
real-life analogy
Picture it
You don't check every name to find everyone called 'Carter'. You open at C, then flip to Ca — and now every name in front of you starts with 'Ca'. You didn't search for them; you just navigated to the right place and there they all were. A trie is that phone book, built out of pointers.
interactive visualization
Watch it run
Pick a word set: 1 = car/card/cat/dog, 2 = to/tea/ted/ten/in/inn, 3 = go/gone/good/god.
double ring = a word ends here
Store these words: to, tea, ted, ten, in, inn. A trie doesn't store them as separate strings — it stores them as *paths*, and words that start the same way share the same path.
step 01/27
- comparing
- moving
- found it
space · play ← → · step
| 1 | class Node { |
| 2 | constructor(char) { |
| 3 | this.char = char; |
| 4 | this.children = {}; // one child per next letter |
| 5 | this.isWord = false; |
| 6 | } |
| 7 | } |
| 8 | |
| 9 | function insert(root, word) { |
| 10 | let cur = root; |
| 11 | for (const ch of word) { |
| 12 | // Reuse the path if it already exists — that's the whole point. |
| 13 | if (!cur.children[ch]) cur.children[ch] = new Node(ch); |
| 14 | cur = cur.children[ch]; |
| 15 | } |
| 16 | cur.isWord = true; // a word ends here |
| 17 | } |
| 18 | |
| 19 | function startsWith(root, prefix) { |
| 20 | let cur = root; |
| 21 | for (const ch of prefix) { |
| 22 | if (!cur.children[ch]) return false; // no such path |
| 23 | cur = cur.children[ch]; |
| 24 | } |
| 25 | return true; // every word below this node has the prefix |
| 26 | } |
variables right now
- words
- to tea ted ten in inn
the dry run · every step, in words
27 stepscomplexity
What it costs
- best case
- O(L)
- average
- O(L)
- worst case
- O(L)
- extra memory
- O(total characters)
Insert and search cost O(L), the length of the *word* — completely independent of how many words the trie holds. A million words or ten, looking up 'card' takes four steps. The price is memory: a node per character, though shared prefixes claw a lot of it back.
- O(1) · this one
- O(log n)
- O(n)
- O(n log n)
- O(n²)
common mistakes
Common traps
Forgetting the 'is a word ends here' flag.
Without it you can't tell 'car' (a real word) from the 'car' inside 'card' (just a prefix). The path existing doesn't mean the word exists.
Storing the whole word at each node.
That throws away the entire benefit. The word IS the path — that's what makes prefixes shared and memory manageable.
Using a fixed 26-slot array per node without thinking.
Fast, but 26 pointers per node adds up brutally on a sparse trie. A hash map per node uses far less memory when most letters are unused.
Reaching for a trie when a hash set would do.
A hash set does exact lookup in O(1) with far less memory. Only use a trie when you need *prefixes* — autocomplete, wildcards, longest-common-prefix.
quiz
Check yourself
Three questions. Get them all right to finish the lesson.
+100 XP01Where is the word actually stored in a trie?
02How long does it take to find every word starting with 'ca'?
03When should you NOT use a trie?
practice
Solve it on LeetCode
You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.