Trie Data Structure for Prefix Matching
You'll learn: How tries efficiently store and retrieve strings by prefix, making them ideal for typeahead suggestions in search systems.
What Is a Trie?
A trie (pronounced "try," from retrieval) is a tree-like data structure where each node represents a single character of a string. Words sharing common prefixes share the same path from the root, making prefix lookups extremely fast.
Think of it like a filing system: instead of storing "cat," "car," and "card" separately, you store c → a, then branch into t (for "cat") and r (which branches further into "car" and "card"). All words starting with "ca" share the first two nodes.
Why Tries Excel at Typeahead
When a user types "se" into a search box, you need to find all matching suggestions instantly. With a trie:
- Navigate from root → 's' → 'e' (2 operations)
- Collect all words in the subtree below 'e'
This beats scanning millions of strings or even binary search. The lookup time is O(m) where m = prefix length, independent of total vocabulary size.
Key Properties
- Space-efficient for shared prefixes (many words → fewer nodes)
- Fast prefix matching: Walk down the prefix path once
- Easy enumeration: All completions live in one subtree
- Supports ranking: Store metadata (frequency, popularity) at terminal nodes to rank suggestions
Storage Considerations
Each node may store:
- Character or edge label
- Children pointers (array or hashmap)
- End-of-word flag
- Metadata (completion count, score)
For massive vocabularies, tries can be memory-intensive, but compression techniques (radix tries, LOUDS) help at scale.
Key Takeaway:
Tries organize strings by shared prefixes, enabling O(prefix_length) lookup for typeahead suggestions—far faster than scanning or searching unsorted data.