A trie (prefix tree) stores strings by sharing common prefixes across sibling branches. Each edge represents a character and every path from the root to a terminal node describes one word.
- Each path from the root to a marked leaf/node forms a word.
- Each node (except the root) holds a character value and optional termination flag.
- Descendants of any node share the prefix associated with that node.
Insert: follow or create edges for each character and mark the terminal node.Search: walk the edges and confirm the terminal marker at the end of the word.StartsWith: like search but without requiring a terminal marker.
- Predictable O(L) insert/search where L is the word length, independent of total word count.
- Supports alphabetical iteration and prefix queries without extra sorting.
- Avoids hash collisions and offers deterministic traversal order.
- Autocomplete engines and search suggestions.
- Contact search on mobile devices and directory lookups.
- Spell-checkers, predictive text, and DNA sequence prefix matching.
- IP routing tables (compressed tries like radix/patricia trees).
- Higher memory footprint compared to hash maps due to child pointers per alphabet symbol.
- Requires careful handling of sparse alphabets; consider compression or ternary search trees for efficiency.
Trie.go: core data structure implementation in Go.longest_common_prefix.go: leverages trie logic for prefix computations.questions/: interview-style problems to practice trie-based solutions.