Overview
A trie (prefix tree) stores strings by shared prefixes, enabling O(k) insertion, lookup, and prefix search.
Analogy
A dictionary organized by letters: branch at 'a', then 'ap', then 'app', then 'apple'.
Step-by-step
- Each node has children dict (or array of 26) and an is_end flag.
- Insert word: for each char, move to/create child node; mark last as end.
- Search exact: traverse chars; check is_end at last node.
- Prefix search: traverse prefix; return True if all chars found (no is_end check).
Visual
Insert 'cat','cap': root→c→a→t(end), root→c→a→p(end); shared prefix 'ca'.
Common mistakes
- Marking is_end only at very last character node (correct), not at intermediate nodes.
- Deleting from trie requires careful removal — don't delete shared prefix nodes.
Practice questions
- Implement autocomplete: return all words with a given prefix.
- Use a trie for longest word search in a dictionary.
Time
O(k) per operation (k = word length)
Space
O(ALPHABET × n × k) worst case
AI Wisdom