Type "mum" into a train booking app. Instantly: Mumbai Central, Mumbai CST, Mumbra... every suggestion starting with exactly what you typed, out of thousands of station names, faster than your next keystroke.
Let's try to build that with what we have. A hash set of station names answers "does Mumbai Central exist?" in O(1) — lesson 5's pride. But "everything starting with mum"? Here the hash betrays us, and for a deep reason: hashing deliberately scatters similar keys far apart (tiny key change → totally different bucket — remember?). The mum-words are sprayed across all buckets, and collecting them means scanning every key. O(n).
The very property that made hashing fast makes prefixes impossible. Prefix queries need the opposite of scattering: words that start alike should live together. Today's structure is built from exactly that sentence.
The idea: let the path spell the word
Think about how YOU find "mango" in a dictionary: first the M section, inside it the MA pages, inside those MAN... Each letter narrows you into a smaller section that all shares the letters so far. Now make that physical: build a tree where each edge carries one character, and a word is stored... nowhere, as a unit. The word IS the path from the root.
"cat" is the journey root → c → a → t. This structure is called a trie (from retrieval — say "try", to keep it apart from "tree" in conversation).
Sharing: why 10 characters need only 5 nodes
Insert "can", "cane", "cat" — 10 characters of input — and count the nodes in the picture: c, a, n, e, t. Five. All three words ride the same c → a path; "cane" just extends "can" by one node; "cat" branches off after the a.
This sharing is not an optimisation bolted on afterwards — it IS the structure: common prefixes are stored exactly once, which forces every word starting with "ca" to live below the same node. The mum-problem is already solved by the shape itself; we just have to finish the details.
A bug in our design — and the flag that fixes it
Details first, and one of them bites. Suppose we insert ONLY "cart". Now search for "car": walk c → a → r... every step succeeds. So is "car" in our dictionary?
No! Nobody inserted it — the c-a-r path exists only as scaffolding on the way to "cart". A bare "did the walk succeed?" check confuses prefixes with words. So each node needs one extra bit: does some inserted word END here?
"Can't leaves be the word-ends?" Look at the picture again: "can" ends at the n node — an internal node, because "cane" continues through it. Words end mid-path whenever one word extends another, so the flag must be explicit, on any node.
A trie in 25 lines
The leanest Python trie is nested dictionaries — each node is a dict from character to child node, with a special key playing the end-of-word flag:
class Trie:
END = "#" # flag key: "a word ends here"
def __init__(self):
self.root = {}
def insert(self, word): # O(word length)
node = self.root
for ch in word:
node = node.setdefault(ch, {}) # walk, creating if absent
node[self.END] = True # plant the flag
def _walk(self, s): # shared walker
node = self.root
for ch in s:
if ch not in node:
return None # path breaks: s isn't here at all
node = node[ch]
return node
def search(self, word): # exact word?
node = self._walk(word)
return node is not None and self.END in node
def starts_with(self, prefix): # any word with this prefix?
return self._walk(prefix) is not NoneRead search and starts_with side by side — they share the walk and differ in ONE check: the flag. That one check is the entire cart/car story, turned into code.
Dry run: search and starts_with
inserted: "can", "cane", "cat"
search("can"): c ok -> a ok -> n ok -> flag at n? YES -> True
search("ca"): c ok -> a ok -> flag at a? no -> False
starts_with("ca"): c ok -> a ok -> path exists -> True
search("cab"): c ok -> a ok -> b? not a child -> False
search("dog"): d? not a child of root -> FalseFive queries, and among them every possible outcome: word found, prefix-but-not-word, prefix exists, path breaks midway, path breaks immediately. Trace these five once with a pen and the trie holds no further mysteries.
Costs: word length beats dictionary size
Every operation walks one character per step, so for a word of length L: O(L) — insert, search, starts_with, all of them. Notice what's absent from that formula: n, the number of stored words. Searching "apple" is five steps whether the trie holds ten words or ten lakh.
| Operation | Trie | Hash set | Sorted list |
|---|---|---|---|
| Insert / search a word | O(L) | O(L) average* | O(L log n) |
| All words with prefix p | O(len(p) + matches) | O(n) — scan everything | O(log n + matches) |
| Memory | high — nodes + child maps | low | lowest |
(*hashing also reads all L characters — so the trie's edge is NOT raw lookup speed; it's the prefix row.) And note the quiet third contender: a sorted list + binary search answers prefix queries respectably (all "mum" words sit adjacent!). If the data is static and memory is tight, saying "a sorted array is honestly competitive here" is a credibility move, not a weakness.
Autocomplete: the payoff
Back to the booking app. Everything starting with "ca": walk 2 steps to the "ca" node, then collect every flagged node in that subtree:
def suggestions(trie, prefix):
node = trie._walk(prefix)
if node is None:
return [] # nothing starts with this
out = []
def collect(nd, path): # DFS below the prefix node
for key, child in nd.items():
if key == Trie.END:
out.append(prefix + path) # a word ends here
else:
collect(child, path + key)
collect(node, "")
return out
t = Trie()
for w in ["can", "cane", "cat"]:
t.insert(w)
print(suggestions(t, "ca"))Result
['can', 'cane', 'cat']
Cost: O(len(prefix) + size of the matching subtree) — you touch the matches and nothing else. No other basic structure has this property. It's why search boxes, spell checkers, phone T9 dictionaries and IP routers (longest-prefix match on bit-tries) all run on tries.
What if...?
What if memory matters? What does a trie really cost? Time to pay the bill. Every node is a dict object; every character of every unshared suffix gets one. A million long words with little prefix overlap → millions of dicts, each with Python object overhead. The flat strings might take 10 MB; the trie, hundreds. So the honest summary: gain prefix superpowers, pay memory — and if the workload has NO prefix queries, the hash set wins outright. (Production tries compress single-child chains — radix trees — and use arrays instead of dicts; know the names, skip the implementation.)
What if I insert the same word twice? The walk finds every node already present and re-plants the same flag — idempotent, harmless. (To count duplicates, store a number instead of True.)
What if the alphabet is huge — Unicode, whole words? Dict-based nodes don't care (they store only what exists); array-based 26-slot nodes do. This is exactly the dict-vs-array node trade: memory frugality vs fixed-slot speed.
What if case matters — "Mumbai" vs "mumbai"? Different paths! Normalise on the way in (lowercase everything) or accept the split — but decide consciously; this silently breaks real autocompletes.
Common mistakes
- No end-of-word flag — every prefix of a stored word looks stored (the cart/car bug).
- Marking word-ends only at leaves — misses words that extend into longer words ("can" inside "cane").
- Conflating
searchandstarts_with— the flag check is the entire difference. - Claiming the trie "beats hashing at lookup" — both are O(L); the trie's edge is prefixes only.
- Using a trie with no prefix workload — paying its memory bill for nothing.
- Skipping case/Unicode normalisation.
How do I recognise trie problems?
- "starts with / prefix / autocomplete / type-ahead / spell-check" → trie, almost by name.
- "implement insert / search / startsWith" → the 25-liner above, verbatim — a literal product-company staple.
- "count words with a given prefix" → trie with a counter per node, incremented during insert (in your Practice Zone).
- "longest common prefix of many strings" → walk the trie from the root while nodes have exactly one child.
- Anything sequence-with-shared-beginnings: digits (phone routing), bits (IP addresses), file paths.
Counter-clue: exact-match only → hash set; ordered ranges → BST. The trie is the prefix specialist, and specialists shouldn't do general work.
Quick revision
| Operation | Cost | Note |
|---|---|---|
| Insert word (length L) | O(L) | creates only unshared suffix nodes |
| search / starts_with | O(L) | independent of dictionary size; differ by the flag check |
| Autocomplete prefix p | O(len(p) + matches) | touches matches only |
| Memory | O(total unshared characters) | the price of the superpower |
One thing to remember
Hashing scatters similar keys apart; a trie pulls them together — the path spells the word, so everything sharing a prefix lives under one node. Choose by that one axis and the trie-vs-hash decision makes itself.
Practice Zone — PYQs from real selection rounds
Six MCQs, then two builds: the classic insert/search/startsWith trie, and the counting trie that answers prefix-counts in O(len(prefix)).
In a trie, where is a word actually stored?
Asked in
Searching a trie of 10 lakh words for the word "apple" costs:
Asked in
Why does a trie node need an end-of-word flag?
Asked in
Autocomplete ("show every word starting with 'pra'") is efficient in a trie because:
Asked in
The main COST of a trie compared to a hash set of the same words is:
Asked in
Insert "can", "cane", "cat" into an empty trie. How many nodes exist (excluding the root)?
Asked in
Hands-on tasks:
Implement a trie with insert(word), search(word) and starts_with(prefix). search("car") must be False after inserting only "cart".
Asked in
Extend the trie so count_prefix(p) returns how many inserted words start with p — in O(len(p)), NOT by enumerating the subtree. Insert "can", "cane", "cat", "dog"; count_prefix("ca") should be 3.
Asked in
FAQ
Trie vs BST for storing words?
A BST of words costs O(L log n) per lookup (log n comparisons, each up to L characters) and answers range queries; a trie costs O(L) flat and owns prefixes. Autocomplete → trie. "Alphabetically between X and Y" → tree. Plain membership → hash set beats both on simplicity.
What about the 26-children-array trie I've seen in books?
The array implementation: each node holds a 26-slot child array (lowercase English) — O(1) child hops, but 26 pointers paid per node even when one is used. The dict version pays only for existing children. Array = speed and predictability; dict = memory frugality. Both are real tries.
What is a radix tree / compressed trie?
A trie where chains of single-child nodes collapse into one edge labelled with the whole substring — "mumbai" becomes m→umbai instead of six nodes. Same queries, far fewer nodes. Routers and databases use them; interviews only expect you to know why they exist (the memory bill).
Can tries store things other than words?
Anything sequence-shaped: digits (phone-prefix routing), bits (IP longest-prefix match is a bit-trie walk), file paths, DNA fragments. If it reads left to right and shares beginnings, a trie will index it.
Prefixes conquered. Next, a structure that answers exactly one question — "same group or not?" — in practically constant time — Lesson 11: Union-Find →