Store a dictionary by its shared fronts and every prefix question — search, starts-with, autocomplete — costs one map hop per typed letter, no matter how many words you loaded. Meet the trie: the one data structure the problem statement practically draws for you.
Chapter 4 handed you the hash map: exact membership in one lookup. Chapter 11 handed you tree DFS. A trie is what happens when those two chapters have a child: a tree whose every node is a tiny hash map keyed by letters, so that walking down the tree spells a word — and any question shaped like "what starts with…?" gets answered while the user is still typing.
This is the smallest pattern chapter in the book by problem count — three canonical problems — and one of the highest-yield per minute, because trie problems are nearly impossible to solve well with anything else and nearly automatic once you've built one. We'll build the node, watch shared prefixes pay rent, add autocomplete and a wildcard, and finish with the trick that turns Word Search II from a slideshow into a sprint.
A hash set of n words answers search("interview") in O(L) — hash the word, one bucket, done (L is the word's length; you pay to read it, nothing more). Now ask a slightly different question: does anything in the dictionary start with "inter"? The hash set goes quiet. Hashing is deliberately structure-destroying — "inter" and "interview" land in unrelated buckets — so your only move is to scan all n words: O(n · L). Ask for the actual list of completions, once per keystroke, and you're rebuilding Google's autocomplete with a for-loop.
A sorted array does better: binary search (Chapter 9) finds where the "inter…" block begins in O(L log n), and the completions sit contiguously after it. That's a respectable answer for a frozen dictionary, and worth saying out loud in the room. But it re-searches from scratch on every keystroke, and inserting new words into a sorted array is an O(n) shove.
The trie's move is to stop treating the word as an opaque key and start treating it as a path: first letter picks a child of the root, second letter picks a child of that, and so on. Prefixes stop being a question you compute and become an address you walk to. The whole chapter is three problems deep:
The entire data structure is one two-field node, repeated:
Notice what's missing: the node stores no word, not even its own letter (the letter lives on the key in the parent's map). A node's identity is the path that reaches it — the root is the empty prefix, the node two hops down i → n is the prefix "in". Words aren't payloads filed in the tree; they're addresses. That's why prefix queries are free: asking about "inter" means walking to "inter", and either the address exists or it doesn't.
Compare it to Chapter 12's BST for one second: a BST orders whole keys by comparisons, so search costs O(log n) comparisons of entire words. A trie spends one map hop per character and never mentions n at all. For string keys with shared structure, the trie is playing a different sport.
Here's the accounting that makes the structure earn its memory. Take eight words with a family resemblance: in, into, inter, intern, internal, internet, interval, interview. Written out, that's 50 letters. Inserted into a trie, it's 17 nodes — because "inter" is spelled once and six words ride it. Every shared front is stored exactly once, and a new word costs only the letters where it diverges from everything already present.
Feed the words in below and watch the arithmetic happen: reused nodes flash ochre, new nodes appear green, and the gap between "letters fed" and "trie nodes" is the rent the sharing pays.
Worst case, for honesty's sake: words that share nothing ("zebra", "quilt", "fjord") reuse nothing, and node count equals letter count. The trie's compression is a bet on shared fronts — which real dictionaries, URL sets, and file paths win overwhelmingly, and adversarial inputs don't. Sharing is also fronts only: "interview" and "overview" share a suffix and the trie couldn't care less. (Suffix structures exist; interviews almost never ask for them.)
Every trie operation is the same loop — follow one child per character — with a different attitude about missing children:
All three cost O(L) — one map hop per letter of the argument, and the size of the dictionary never appears in the bound. A trie holding ten words and a trie holding ten million answer startsWith("inter") in the same five hops. That sentence, said out loud, is worth real points: it shows you know why you picked the structure, not just that you did.
Autocomplete is the two patterns of this Part shaking hands. Step one: walk the typed prefix — O(|p|), as above. Step two: everything below the node you landed on is the set of completions, so run Chapter 11's DFS over that subtree and collect every stamped node. Total cost: O(|p| + answer) — you pay for the typing and for the results, and for nothing else in the dictionary. That's the whole engineering story behind the dropdown under every search box you've ever used (real ones bolt on ranking; the skeleton is this).
Type into the box below. The green path is your walk; the bright subtree is the spill; the counters are the receipt.
Design Add and Search Words Medium is Implement Trie with one twist: search("b.d") must match "bad", "bed", "bud" — . means any letter. The plain walk breaks at the dot, because the whole point of the walk was that each character picks one child, and a dot refuses to pick.
The fix is the obvious one, and it's a preview of Chapter 18's whole personality: when you can't choose, try every choice. At a literal character, follow the one child as usual; at a dot, recurse into every child, succeeding if any branch survives the rest of the pattern. The walk becomes a DFS. Cost: still O(L) on dot-free queries; each dot multiplies the frontier by up to 26, so a pattern of all dots degrades toward visiting the whole trie. Interviewers know this and will ask — the answer is "exponential in the number of dots, and the problem keeps dots scarce, so in practice it's fine." Saying the bound and why it doesn't bite is the whole point of the follow-up.
One habit worth keeping: this branch-at-the-wildcard move is the same "walk the structure, fork on uncertainty" shape you'll use on the letter board in the next section. The trie doesn't change; only the walker gets braver.
Word Search II Hard: given a letter grid and up to 10⁴ words, return every word you can trace through adjacent cells. The honest first answer is Chapter 18's Word Search — a backtracking DFS per word — run 10⁴ times. Cost: (one full board search) × (number of words). The board gets re-explored from scratch for every word, even though "oat" and "oath" walk the identical first three cells. That repetition should itch.
Flip the loop. Instead of searching the board once per word, build a trie of all the words and search the board once, walking board and trie in lockstep: from each cell, DFS carries a trie node; stepping onto a neighbor asks that node's children map for the neighbor's letter. One map hop now checks the path against every word simultaneously — and a missing child kills the branch for all 10⁴ words at once. That's the pruning. Finding a stamped node en route means "a whole word ends here": record it and keep walking, since "oath" may continue past "oat".
Race the two plans below on the same board and the same seven words. Green cells are hops the trie accepted; red are wasted visits. The counters are the argument.
Seven words on a 4×4 board already shows a gap; at 10⁴ words the naive plan multiplies its work ten-thousand-fold while the trie plan's board traversal doesn't grow at all — more words just make the trie slightly bushier. Two polish moves interviewers love to hear: un-stamp a word once found (clear its flag, or store-then-null the word at the node) so it's never reported twice, and snip childless nodes on the way back up so dead branches stop attracting future DFS visits. Both are two lines.
The recognition summary. A trie wants three things to be true: the keys are sequences over a small alphabet (letters, digits, bits — IP prefixes and phone numbers count); the queries are prefix-shaped (starts-with, autocomplete, longest-common-prefix, many-patterns-one-text); and there are enough words sharing fronts for the structure to pay rent. Miss the second condition and you've built decoration: exact-membership-only questions belong to Chapter 4's hash set, which is simpler and faster in constants. A one-off "does any word start with p" over frozen data is also legitimately answerable by sort + binary search (Chapter 9) — mention it, then note the trie wins the moment queries stream in character by character or words keep arriving.
Costs, stated plainly: space is O(total letters) nodes in the worst case, and each node carries a map. With a fixed 26-letter alphabet you'll see the classic children = array of 26 variant — faster hops, but 26 slots allocated per node whether used or not. A dict/HashMap spends memory only on children that exist. Either is acceptable in an interview; naming the trade-off is the flex. And a wave forward: this "pay memory up front to make queries cheap" bargain is Part III's recurring theme — Chapter 14's heap makes the same deal next, promising even less structure for even cheaper maintenance.
The pattern, as a whiteboard skeleton:
The flagship is Implement Trie (Prefix Tree) Medium — the rare LeetCode problem that is the pattern, no costume. Both versions below follow the skeleton line by line: a two-field node, an optimistic insert, and one shared walk that search and startsWith each finish with a single question. The Python walk is a loop that bails on a missing child; the Scala walk is the same idea folded over an Option — the None short-circuits the moment the path breaks, which is exactly the "fell off the trie" case.