Back to DSA DashboardConcept Mastery
DSA Core Concept
Trie
A Trie (pronounced 'try'), also known as a prefix tree, is a specialized tree-based data structure used to store an associative search space of strings. Each node represents a character, and paths from root to node represent string prefixes.
Why It Exists
Searching for a word of length L in a hash map takes O(L) on average, but could degrade. More importantly, hash maps cannot find words sharing common prefixes. Tries resolve prefix searches in O(L) time.
Intuition for Beginners
“Think of looking up a word in a paper dictionary. You skip to the first letter, then trace down matching characters. You don't read every word in the book.”
Visual Explanation
Trie structure for keys ["cat", "cap", "do"]:
[Root]
/ \
(c) (d)
/ \
(a) (o)* <- End of word
/ \
(t)* (p)* <- End of wordComplexity Analysis
| Operation | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Insert | O(L) | O(AL * L) | L = word length, AL = alphabet size |
| Search | O(L) | O(1) | Fast character chain checks |
| Prefix Check | O(L) | O(1) | Instant lookup without scanning ends |
| Space Overhead | - | O(N * AL) | Nodes allocate children pointers |
Production & Real World Applications
- •Search Auto-completers: Finding matching words as user types keys.
- •IP Routing Tables: Finding the longest matching prefix for network routing packets.
Algorithmic Patterns
Character Array Children
Using size 26 index arrays to map character ASCII values ('a' -> index 0) for O(1) link jumps.
Defending the Design (Interview Q&A)
Q:Explain the space-time tradeoff of a Trie compared to a Hash Table.
A Trie resolves prefix queries (e.g. finding all words starting with 'dev') which hash tables cannot do. However, Tries require more memory because each node allocates pointers for potential children (e.g., 26 pointers in English), which can be sparse.
Common Traps & Mistakes
- ⚠️Forgetting to set the `isEndOfWord` flag when inserting nodes.
- ⚠️Allocating memory recursively without deleting unused branch nodes (memory leak).