Why it matters
Autocomplete, spell check, IP routing, and search indexing all use tries or trie variants. Understanding when to reach for one instead of a hash map is real engineering skill.
The architecture
Node structure: character, children map (letter → child node), terminal flag (marks end of a stored word).
Insert: walk from root, create children as needed for each character.
Lookup: walk children; if any missing, key absent. If path ends at terminal, key present.
How it works end to end
Applications: autocomplete (find all words with given prefix), spell check (nearest word within edit distance), IP routing (longest prefix match), dictionary storage.
Compressed trie (Patricia trie, radix tree): merge chains of single-child nodes. Space-efficient. Used in Linux kernel, IP tables.
Suffix trie / suffix tree: store all suffixes; enables substring queries. Ukkonen's algorithm builds in linear time.