Data Structures #5 — Trie (Prefix Tree)

A Trie (prefix tree) stores strings character by character, sharing common prefixes. It enables O(k) lookup where k is the key length — independent of how many keys you've stored. Tries power autocomplete, spell checkers, and IP routing.

1. Basic Trie — Insert, Search, startsWith

2. Autocomplete — Find All Words with a Prefix

3. Delete a Word from a Trie

4. Count Words with a Given Prefix

5. When to Use a Trie vs Hash Map

Key Takeaways

• Trie = tree where each character is a node, and isEnd marks complete words.
• insert/search/startsWith are all O(k) where k = key length.
• Autocomplete: navigate to prefix node, then DFS to collect all complete words.
• Delete: unset isEnd, prune nodes that have no children and aren't an end.
• Memory-heavy for large alphabets — compress with radix tree (Patricia trie) if needed.
• Tries shine for prefix search, autocomplete, spell checkers, and IP routing tables.

Next: FP #1 — compose() & pipe() — implement function composition and build transformation pipelines.