Overview
Trie (prefix tree) strings nodes mein characters represent karte hue store karta hai, words aur prefix search ke liye.
Analogy
Jaise dictionary jo characters par branch karta hai—'ca' jaankar 'cat' aur 'car' jaldi milte hain.
Step-by-step
- Har node mein children dict aur is_end flag
- insert: word[i] par walk karo, nahi hai toh create karo
- search: puri word walk kar sake aur is_end True ho
- startsWith: prefix walk ho sake toh True
Visual
insert("cat","car","dog")
root
/ ...
c d
| |
a o
/ \ ... \
t r g
Common mistakes
- search aur startsWith mein is_end ka fark bhool jana
- Delete operation complex hai bhool jana
Practice questions
- Auto-complete implement karo (prefix → candidate words list)
- Dictionary mein maximum XOR words dhundo
Space
O(ALPHABET_SIZE * L * N)