← Tries · guided lesson
Tries
the story
Trie (prefix tree)
Every tool here exists because something was too slow or broke without it. Here is what.
In March 1959 René de la Briandais presented "File searching using variable length keys": store keys letter by letter in a tree, so a lookup reads one letter per level. In September 1960 Edward Fredkin independently described the same idea in "Trie Memory" (Communications of the ACM) and coined the name from re-trie-val. Fredkin meant it to be said like "tree"; many people say "try" to keep the two apart.
the problem it solved
Looking up keys of different lengths — words, codes — in time that depends on the key's length, not on how many keys are stored.
why it matters: without it
Every keystroke in a search box would rescan the whole list, or need a sorted copy plus a binary search per prefix.
sources: R. de la Briandais — File searching using variable length keys (Western Joint Computer Conference, 1959) ↗ · E. Fredkin — Trie memory (Communications of the ACM, 1960) ↗ · NIST Dictionary of Algorithms and Data Structures — trie (name and Fredkin's note on pronunciation) ↗ · Trie — history (de la Briandais 1959; Fredkin's independent 1960 description) ↗
also in this chapter: Binary trie (bitwise trie) · Trie-guided backtracking (many words at once)
the idea
The idea in 30 seconds
A trie (prefix tree) stores words letter by letter: each edge is a letter, each root-to-node path spells a prefix.
Words that share a beginning share the same path, so "car", "card" and "care" reuse the nodes c → a → r.
Any lookup walks one node per letter: O(L) for a word of length L, no matter if you stored 10 words or 10 million.
picture this
Your phone's contact search: type "Pr" and the list instantly narrows to Pradeep, Pranav and Priya. Nothing scans every contact — each letter you type is one step down a path those names share.
watch it
Insert words — shared prefixes reuse nodes
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Insert words — shared prefixes reuse nodes
New letters grow new branches; known prefixes are walked, not copied. Boxes mark where a word ends.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
search(word) vs startsWith(prefix)
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
search(word) vs startsWith(prefix)
Both walk the same path. Only search also demands the end-of-word box at the last letter.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 10
Read it once. Say it out loud once. Bas.
The root is empty. A node is reached by a path of letters; the node itself stands for that prefix.
key idea 2 of 10
Read it once. Say it out loud once. Bas.
An end-of-word flag (isEnd) is essential: without it you can't tell the stored word "app" from the mere prefix of "apple".
key idea 3 of 10
Read it once. Say it out loud once. Bas.
search(word) = the path exists and isEnd is true. startsWith(prefix) = the path exists. Same walk, different final check.
key idea 4 of 10
Read it once. Say it out loud once. Bas.
Children as Node[26] = fastest and simplest for lowercase a–z, but every node pays for 26 slots. HashMap<Character, Node> = only the letters that exist, any alphabet, slower constant.
key idea 5 of 10
Read it once. Say it out loud once. Bas.
Add counters for free superpowers: pass (words through this node) answers "how many words start with p?" in O(L), and makes delete easy.
key idea 6 of 10
Read it once. Say it out loud once. Bas.
Autocomplete = walk to the prefix node, then DFS its subtree. Visiting children a→z returns results already sorted. For top-k suggestions, store the k best words on each node at insert time.
key idea 7 of 10
Read it once. Say it out loud once. Bas.
A wildcard . turns search into a DFS that branches only at the dots; normal letters still follow one child.
key idea 8 of 10
Read it once. Say it out loud once. Bas.
Tries aren't only for letters: a binary trie stores numbers bit by bit (high bit first) and answers max-XOR queries greedily.
key idea 9 of 10
Read it once. Say it out loud once. Bas.
Many words + one grid (Word Search II) → put the words in a trie and let it prune the DFS: stop as soon as no word has the current prefix.
key idea 10 of 10
Read it once. Say it out loud once. Bas.
When the match runs backwards, insert the words reversed — Palindrome Pairs reads one word forwards down a trie of reversed words.
spot the pattern
When you see this, think this
"prefix", "starts with", "autocomplete", "suggestions", "typeahead"
Trie — walk to the prefix node
Search many words at once in a grid or a string
Put all words in a trie, run one DFS that follows the trie
Wildcards like
.matching any letterTrie + DFS that branches only at the wildcard
Replace words by their shortest root / dictionary prefix
Trie: stop at the first end-of-word node on the walk
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Forgetting
isEnd: thensearch("app")returns true after inserting only "apple". - Returning
truefromsearchjust because the walk finished — the final node must also be an end of word.
quick check
One question. No pressure.
You insert only "apple". What do search("app") and startsWith("app") return?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Implement Trie (Prefix Tree)
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What does one trie node hold, and what does a node stand for?
Question 1: What does one trie node hold, and what does a node stand for?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.