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 wordTrie Search
Insert characters 'c', 'a', 't' node paths stemming from the root.
Complexity 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
Using size 26 index arrays to map character ASCII values ('a' -> index 0) for O(1) link jumps.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Forgetting to set the `isEndOfWord` flag when inserting nodes.
- ⚠️Allocating memory recursively without deleting unused branch nodes (memory leak).