🌲 Trie

A trie is a tree keyed on characters, giving $O(L)$ prefix lookups. Useful for autocomplete, word searches, and any "prefix" question. Often combined with backtracking on grids.

This category contains 3 problems. Use the patterns below to recognize what's being asked, then jump to the problem list at the bottom.

---

🧠 Key Patterns

• Insert / Search / StartsWith — The base operations every trie problem builds on.
• Word Search II — Trie + DFS in a grid — bulk match many words in one pass.
• Replace Words / Longest Common Prefix — Walk the trie until you fall off.
• Suffix Trie / Suffix Array — Substring queries on a single string.
• XOR Maximum / Bit-Trie — Trie keyed on bits for max-XOR pair problems.

⚠️ Common Pitfalls

• Memory: each node has up to 26 (or 128) children. For huge dictionaries prefer a hash map per node.
• Forgetting the "end of word" flag — startsWith and search diverge here.

---

📚 Study Resources

📺 Videos

• NeetCode — Trie playlist
• William Fiset — Tries

📖 Books

• Algorithms — Sedgewick — Ch. 5.2 (Tries)

🌐 Articles & References

• LeetCode — Trie Patterns

---

💻 All Trie Problems

📄️Big Countries

LeetCode 595 | Difficulty: Easy

📄️Implement Trie (Prefix Tree)

LeetCode 208 | Difficulty: Medium

📄️Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.