Trie data structure - underrated but powerful

Tries don't come up super often but when they do, nothing else works as well:

When to use:

• Autocomplete / prefix search
• Word dictionary with wildcard search
• Longest common prefix
• Word search in a grid (Trie + backtracking)
• IP routing (binary trie)

Implementation tips:

• Use HashMap<char, TrieNode> for children (cleaner than array)
• Always add an isEnd flag
• Consider storing the word itself at leaf nodes

Must-solve problems:

1. Implement Trie
2. Word Search II
3. Design Add and Search Words
4. Replace Words

If you can solve #2, you can handle any Trie interview question.