Trie (Prefix Tree)
A tree for storing strings character-by-character for fast prefix lookups.
What is this pattern?
A Trie stores each character of a string as a node, sharing prefixes across words. Insert and search run in O(L) where L is the word length — independent of the number of words stored. Ideal for autocomplete, spell checking, and word search problems.
When to use it
- Prefix matching or autocomplete
- Storing a dictionary of words for repeated lookups
- Word search in a 2D board (Trie prunes dead-end paths)
- Finding longest common prefix across many strings
Key Insight
Each TrieNode holds children[26] (for lowercase letters) and a boolean isEnd. Insert: for each char, create child if absent then move down. Search: traverse and check isEnd. StartsWith: traverse and return true if path exists.
Pro Content
The Java template and practice problems for this pattern are part of the Pro plan. Upgrade to unlock all patterns, 500+ problems, and Aria code reviews.
From ₹3,999 for a year · one-time, no auto-renewal