Trie
Build prefix trees for efficient string operations like autocomplete, prefix matching, and word search.
- • Prefix matching/autocomplete
- • Word dictionary operations
- • Finding common prefixes
- • Word search in grid
- • Single string operations
- • Exact match only (use hash map)
- • Not marking end-of-word nodes
- • Memory overhead for sparse tries
- • Confusing trie traversal with tree traversal
Key Invariant
Each path from root to a marked node represents a stored word — shared prefixes share nodes