Trie (Prefix Tree)
A trie is a tree-like data structure used for efficient retrieval of keys in a dataset of strings. Each node represents a character, and paths from root to marked nodes form words.
Time Complexity
All operations run in O(m) time where m is the length of the key. This is independent of the number of keys stored.
Use Cases
Autocomplete: Fast prefix matching for search suggestions.
Spell Check: Dictionary lookup and correction.
IP Routing: Longest prefix match in routing tables.
T9 Predictive Text: Phone keyboard word prediction.
Genome Analysis: Pattern matching in DNA sequences.
Properties
The root node is always empty. A filled (solid) circle indicates a word-ending node. A hollow circle is an intermediate node. Edge labels show the character for each branch.