Interactive Lab · DSA & Algorithms

Every word that starts with “ca”, in the time it takes to type two letters, the trie

When your phone finishes your word before you do, a trie is usually doing the work. A trie (say “try”, short for retrieval tree) stores a set of words as a tree of characters: follow a path from the root and you spell a word. The magic is shared prefixes“car”, “card” and “cat” all reuse the same c → a nodes, so a common start is stored once. To autocomplete, you walk the prefix and read off everything below it. Watch five words branch in, then look up a prefix.

🎬 Watch the 90-second explainer, then autocomplete a prefix yourself below ↓

▶ The playground, insert words char by char, then autocomplete a prefix

Each node is one character; a path from the root spells a prefix. A green ring marks a node where a word ends. When a new word shares a prefix, we reuse the existing nodes (no new memory) and only branch off where it differs. Scrub to insert the words, then watch a lookup walk a prefix.

step 0 / 0

🧭 Where this fits

Tries answer prefix questions at scale: search-box autocomplete, IP routing tables (longest-prefix match in every router), spell-checkers, and T9 keyboards. The cost-independent-of-dictionary-size property you just proved is why your keyboard suggests words instantly against a 200K-word vocabulary.

The code that's actually running, walk characters, branch only when new

🔮 Predict, then test

Jump to the lookup: it walks c → a and then reads off car, card, catevery word under that node. Predict: the cost of that autocomplete doesn't depend on how many words are stored, only on the length of the prefix plus the number of answers. Inserting or checking a word of length L is O(L)you touch one node per character, no matter how big the dictionary grows. So what does a trie buy you over just storing the words in a hash set, and what does it cost you in return?

The takeaway

Your new mental model of the trie

Words become paths. Each edge is a character; spelling a word means walking root-to-node. The node isn't the letter's valueit's the letter's position in a word.
Shared prefixes, stored once. “car”, “card”, “cat” share c → a; only the tail branches. That's the whole space win, and why prefix questions are trivial.
Length, not dictionary size. Insert, lookup, and delete are all O(L) in the word length, completely independent of how many words the trie holds. A million words don't slow down a five-letter check.
Prefix power a hash set can't match. “All words starting with ca?” is just “walk to that node, collect what's below.” A hash set would have to scan everything. That's autocomplete, spell-check, and IP routing.
The trade-off is memory. Lots of little nodes and pointers cost more than a flat list, so real tries get compressed (radix trees) when space matters.

← Hashing Placement prep →Try: Recursion