aloalgoWhat Is a Trie? No, That's Not a Typo
A trie (pronounced "try") is a tree-like data structure for storing strings. The name comes from "retrieval" — and that's exactly what tries excel at: retrieving strings by prefix incredibly fast. If you've ever used autocomplete, you've benefited from a trie.1. Why Use a Trie?
Tries solve a specific problem: prefix-based operations on a collection of strings.| Operation | HashSet | Trie |
|---|---|---|
| Insert word | O(n) | O(n) |
| Search exact word | O(n) | O(n) |
| Search by prefix | O(n × k) | O(p) |
| Autocomplete (all matches) | O(n × k) | O(p + matches) |
n = word length, k = number of words, p = prefix length
Use a trie when you need:
- Autocomplete / typeahead suggestions
- Spell checking
- IP routing (longest prefix match)
- Word games (Boggle, Scrabble solvers)
- Searching multiple patterns in text
2. How It Works
A trie stores strings character by character, with each node representing a character. Words that share prefixes share the same path from the root.Visual Example
3. Basic Implementation
TrieNode Class
Trie Class
Usage Example
4. Common Operations
Autocomplete: Get All Words with Prefix
Delete a Word
Count Words with Prefix
5. Optimized Implementation
For lowercase English letters only, you can use an array instead of a dictionary for faster access.6. Classic Interview Problems
Word Search II (Multiple Words in Grid)
Find all words from a dictionary that exist in a grid. Trie + DFS is the optimal approach.Design Add and Search Words
Support '.' as wildcard that matches any character.Longest Common Prefix
7. Trie Variations
Trie with Word Count
Bitwise Trie (for XOR problems)
Store numbers as binary strings for maximum XOR problems.8. Complexity Analysis
| Operation | Time | Space |
|---|---|---|
| Insert | O(n) | O(n) |
| Search | O(n) | O(1) |
| Starts With | O(p) | O(1) |
| Delete | O(n) | O(n) recursion |
| Autocomplete | O(p + m) | O(m) |
n = word length, p = prefix length, m = total matched characters
Space for entire trie: O(alphabet_size × total_characters × word_count) in worst case, but typically much less due to shared prefixes.
9. Practice Problems
Core TrieTrie + DFSFinal Thoughts
A trie is essentially a trade-off: more space for faster prefix operations. If you're doing lots of prefix lookups, autocomplete, or searching for multiple patterns, a trie is often the answer. The implementation is straightforward once you understand that each node represents one character and the path from root to node spells out a prefix.Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.