Overview
Trie (prefix tree) — strings efficiently store karta hai shared prefixes ke saath. Autocomplete ka backbone.
Analogy
Jaise dictionary — A section mein sab "A" se shuru wale words, AA section mein "AA" wale...
Step-by-step
- Root node banao (empty string)
- Har character ke liye child node
- Word end mark karo (is_end = True)
- Search: character by character tree traverse karo
Visual
Insert "cat","car","dog"
root -> c -> a -> t (end)
-> r (end)
-> d -> o -> g (end)
Common mistakes
- is_end flag bhool jaana — "car" aur "card" dono hain
- Case sensitivity — lowercase normalize karo
- Space: O(ALPHABET_SIZE * MAX_LEN * N) — can be large
Practice questions
- Basic Trie insert/search/startsWith implement karo
- Autocomplete feature trie se banao