Trie (prefix tree) — insert, search, startsWith, applications (autocomplete, spell check)
WHAT is a Trie?
A node typically holds:
class TrieNode:
children: map<char, TrieNode> # up to 26 for lowercase a–z
isEnd: bool # does a word END here?
HOW the three core operations work
All three walk character by character from the root. They differ only in what they check at the end.
1. insert(word)
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.isEnd = True2. search(word) — is the FULL word present?
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.isEnd # NOTE: not just True3. startsWith(prefix) — does ANY word have this prefix?
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True # path exists ⇒ prefix existsComplexity (derive, don't memorize)
Let = length of the query/word, = number of words, = alphabet size.
Worked Examples
Applications (the WHY it matters)
def autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return []
node = node.children[c]
res = []
def dfs(n, path):
if n.isEnd: res.append(prefix + path)
for c, child in n.children.items():
dfs(child, path + c)
dfs(node, "")
return resOther uses: IP routing (longest-prefix match), T9 / phone keypads, word games (Boggle solver prunes dead prefixes early), DNA substring search.
Common Mistakes (Steel-manned)
Recall Feynman: explain to a 12-year-old
Think of a giant treasure map shaped like a tree. To spell a word you walk along letters: start at the trunk, step onto branch c, then a, then r — now you've spelled "car". If somebody buried treasure (a tiny ✅ flag) exactly where you're standing, "car" is a real word! Words that start the same way walk the same branches before splitting off, so the map never repeats c-a-r twice. Want every word starting with "ca"? Just walk to ca and explore every branch above you — that's autocomplete!
Active Recall
What does each trie node store?
isEnd boolean marking if a word ends there.Why can't "leaf = word" work in a trie?
car can be internal (it has child d for card) yet still be a valid word, so we need an explicit isEnd flag.What is the ONLY code difference between search and startsWith?
search ends with return node.isEnd; startsWith ends with return True (path existence is enough).Time complexity of insert/search/startsWith?
What does the root node of a trie represent?
"".How does autocomplete use a trie?
isEnd=True, prepending the prefix.search("ca") on a trie containing only "car" returns?
a (a.isEnd is False).startsWith("ca") on the same trie returns?
Why is a trie better than a hash set for prefix queries?
How do you (safely) delete a word from a trie?
isEnd; prune nodes upward only if they have no children and are not another word's end.Connections
- Hash Table — fast exact lookup, but no prefix structure.
- Binary Search Tree — string ops vs trie's .
- DFS — used to collect completions in a trie subtree.
- Suffix Tree / Radix Tree (Compressed Trie) — space-optimized relatives.
- Edit Distance — spell-check suggestion generation.
- Longest Prefix Match — IP routing application.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Trie ek aisa tree hai jisme har path root se shuru hoke ek prefix spell karta hai. Soch lo ek bada
map jisme letters ke saath branches hain — c, fir a, fir r chalte jao to "car" ban gaya. Jo
words same tarah se start hote hain (jaise car, card, care) wo same road share karte hain, isliye
prefix bar-bar store nahi hota. Yahi sharing trie ko special banata hai.
Teen main operations hain aur teeno character-by-character root se chalte hain. insert me: agar
child node nahi hai to bana do, end pe isEnd = True set kar do (yani yahan ek poora word khatam hua).
search me: path chalo, agar beech me child missing ho to False; end pe node.isEnd return karo —
sirf path hone se kaam nahi chalega, word end bhi hona chahiye. startsWith me: same chalna, par
end pe sidha True — kyunki prefix ke liye path hona kaafi hai. Bas yahi ek line ka farak hai dono me.
Sabse important trap: search("ca") jab sirf "car" inserted hai to False dega, kyunki "ca" pe koi
word end nahi hota — wo sirf prefix hai. Isiliye isEnd flag zaroori hai, aur isiliye leaf = word maan
lena galat hai (car internal node hai par valid word hai).
Kaam kahan aata hai? Autocomplete — prefix tak chal ke uske subtree me DFS karo, sare words mil jaate
hain. Spell check — search False de to galat spelling. Best baat: har operation hai, words
ki sankhya se independent — ek crore words add karo, lookup phir bhi utna hi fast. Hash set yeh prefix
magic nahi de sakta, isliye trie itna useful hai.