Trie (Prefix Tree)
A tree-based data structure used for efficiently storing and retrieving keys in a dataset of strings.
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Think of a dictionary where you look up words letter by letter. A Trie (pronounced 'try') stores strings such that common prefixes are shared. For example, 'cat' and 'car' share the path 'c' -> 'a'.
Concept
Each node in a Trie represents a character. The root represents an empty string. Moving down from the root adds characters to the prefix. Some nodes are marked as endOfWord to indicate that the path from the root to that node forms a valid word.
How it Works
- Root: Empty node, starting point.
- Children: Map or array linking characters to next nodes.
- EndOfWord: Boolean flag marking a complete string.
- Insertion: Walk down, creating nodes if they don't exist.
- Search: Walk down; if you get stuck, word doesn't exist.
Step-by-Step Breakdown
- Start at root.
- For each character in the word:
- Check if child exists for that char.
- If not, create a new node.
- Move to child.
- Mark the final node as isEnd = true.
When to Use
- Autocomplete/Typeahead systems.
- Spell checkers.
- IP routing (Longest Prefix Match).
- Solving word games (Boggle).
When NOT to Use
- When strings are very long and unique (high space consumption).
- When you only need full string matching (Hash Map is faster O(1) vs O(L)).
How to Identify
Keywords: "Prefix search", "Autocomplete", "Dictionary", "Word Search II".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.