1. One-Liner
A trie (prefix tree) stores strings as paths from the root, sharing common prefixes to support fast insert, search, and prefix queries.
2. The Problem It Solves
Hash sets find exact strings in O(1) average but cannot enumerate by prefix or catch autocomplete efficiently. A trie answers “any word with prefix p?” by walking O(|p|) edges.
3. The Core Idea
Each node maps next character → child. The path from root spells a prefix; a terminal flag marks full words. Compressed tries (radix) collapse long chains to save memory.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Insert: walk/create edges for each character; mark last node end. |
| 2 | Exact search: same walk; require end true. |
| 3 | Prefix search: walk prefix; success if all edges exist. |
| 4 | Delete: tricky—prune dead nodes or decrement counts. |
5. Dry Run Example
Insert “car”, “card”, “cat”. Shared “ca” path splits at r/t; nodes carry end at car, card, cat leaves appropriately.
6. Key Properties
| Aspect | Detail |
|---|---|
| Time | O(L) per op, L = string length |
| Space | Alphabet × nodes; compress for English |
| XOR trie | Bit tries for max xor pair |
7. Where It Is Used
| System | Use |
|---|---|
| Search engines | Autocomplete |
| Routers | IP longest prefix match (Patricia) |
| Competitive programming | XOR max subarray |
8. Interview Tips
Discuss memory vs hash map. Implement count at node for number of strings with prefix. End flag vs path compression edge cases.
9. Comparison with Other Algorithms
| Structure | Prefix queries | Space |
|---|---|---|
| Trie | O(L) walk | High without compression |
| Hashing | Slow scan | Lower |
| DAWG | Linear automaton | Optimal for language |
10. Complexity
| -- | -- |
|---|---|
| Insert / Query | O(L) per string length L |
| Alphabet | σ children per level theoretical |
Implementation Example (PYTHON)
class TrieNode:
def __init__(self):
self.nxt = {}
self.end = False
def trie_insert(root, s):
cur = root
for ch in s:
cur = cur.nxt.setdefault(ch, TrieNode())
cur.end = True
def trie_contains(root, s):
cur = root
for ch in s:
if ch not in cur.nxt: return False
cur = cur.nxt[ch]
return cur.end