Trie (prefix tree)
A trie (prefix tree) stores words character by character. Each edge corresponds to one character, and the path from the root to a node spells out a prefix.
The core idea: shared prefixes share a path. The words "car", "cart" and "card" all travel c → a → r together, then diverge.
Each node holds two things:
- children — character → next node (a Map or a fixed-size array).
- isEndOfWord — whether this node terminates some word.
The isEndOfWord flag is mandatory, and forgetting it is the most common mistake. Without it, after inserting "car" a search for "ca" would also return true — yet "ca" is not in the dictionary, it is merely a prefix. That flag is precisely what preserves the difference between a word and a prefix.
Three core operations — all resting on the same walk:
- insert(word) — start at the root; for each character, create the child if missing and step into it. At the end set
isEndOfWord = true. - search(word) — step into the child for each character; if it is missing,
false. At the end returnisEndOfWord— not merely the node's existence! - startsWith(prefix) — the same walk, but do not check
isEndOfWordat the end; reaching the node is enough.
The only difference between search and startsWith is the last line. Pointing that out in an interview lands well.
Complexity — and this is the whole appeal of a trie:
insert,search,startsWithare all O(L), whereLis the word's length.- Note carefully: the number of words `n` in the dictionary does NOT appear. Searching for
"karpuz"takes the same 6 steps in a trie of 10 words and one of 10 million.
That is an interesting nuance versus a hash set: a hash set is also O(L) (hashing a string means reading all of it), but the trie gives something extra in return — prefix queries.
| Operation | Trie | Hash Set | Sorted array |
|---|---|---|---|
| Exact word lookup | O(L) | O(L) — hash + compare | O(L·log n) |
| "Any word with this prefix?" | O(L) | O(n·L) — scan everything | O(L·log n) — binary search |
| All words with a prefix (autocomplete) | O(L + k) | O(n·L) | O(L·log n + k) |
| Sorted iteration | Free — DFS yields sorted order | O(n log n) — must sort | Free |
| Memory | High — a node per character | Low — strings stored as they are | Lowest |
Memory vs speed — the real trade-off.
The price of a trie is memory. A separate node is created for every character, and each node keeps a Map (or a 26-slot array) for its children. A trie can therefore use several times more memory than a hash set holding the same words — especially when the words share few prefixes.
What do you get back? Prefix operations. In a hash set, "all words starting with kar" requires scanning the whole dictionary — O(n·L). In a trie it is O(L + k): walk to the prefix, then traverse that subtree collecting k results.
There are ways to cut the memory: a radix tree (compressed trie) collapses shared chains, and a DAWG merges identical suffix subtrees. Knowing these names is enough for an interview.
Real-world uses:
- Autocomplete / typeahead — suggestions as you type in a search box. The classic trie application.
- Spell checking — whether a word is in the dictionary, and finding near variants.
- IP routing — routing tables use longest prefix match, which is a bit-level trie (a radix tree).
- Word games — Scrabble, Boggle: while walking the board you ask "is this character sequence a prefix of any word?" and prune hopeless branches immediately. Without a trie that search is impractical.
- T9 and mobile keyboard suggestions, URL/route matching, shell command completion.
Interview tip. A trie question almost always opens the same way: "How would you implement autocomplete?" That is an open invitation to name the trie.
Structure of a strong answer:
1. Reject the alternative and say why: "With a hash set, prefix search means scanning the whole dictionary — O(n·L). That is unacceptable on every keystroke." 2. Propose the trie and explain the mechanism: "In a trie I reach the prefix in O(L), then DFS that subtree to collect suggestions — O(L + k)." 3. Name the trade-off yourself: "The price is memory — a node per character. For large dictionaries I would compress it into a radix tree." 4. Add a practical detail: "In a real autocomplete I would cache the top 5 words of each node's subtree so I do not redo the DFS on every keystroke."
The most common mistake: forgetting the isEndOfWord flag. Without it, search("ca") returns true after inserting "car" — and interviewers test that bug immediately.
A second frequent question: "Trie or hash set?" The key to the answer: if you only need exact lookup, a hash set — simpler and lighter on memory. If you need prefix queries or sorted output, a trie. Choosing a trie without a prefix requirement is over-engineering, and admitting that is a strong signal.