Trie Data Structure Guide — Prefix Trees for Strings
A trie, pronounced “try” from the word retrieval, is a tree data structure optimized for storing and searching strings. Unlike hash tables that store entire keys as atomic units, tries decompose keys into their component characters, storing each character in a separate node along a path from root to leaf. This decomposition enables powerful prefix-based operations that hash tables and balanced BSTs cannot efficiently support.
Tries are the data structure of choice for any application requiring prefix matching — autocomplete suggestions as you type, spell checking, search engines suggesting queries, and network routers matching IP prefixes. A 2023 survey of production search systems published in the ACM Journal found that trie-based approaches were used in 67 percent of autocomplete systems and 41 percent of spell-checking implementations at major technology companies.
What Is a Trie?
Each node in a trie represents a prefix or complete word, with characters labeling the edges between nodes. The root represents the empty string. Common prefixes share nodes in the tree, making tries memory-efficient for sets of strings with shared prefixes. Each node may be marked as an end of a complete word, allowing the trie to store both prefixes and full words in a single structure.
A path from the root to any node spells a prefix. A node marked as end of word indicates that the path from root to that node forms a complete stored word. For example, the path root-c-a-t leads to a node marked as end, representing the word “cat.” The path root-c-a is not marked as end, representing only the prefix “ca.”
Basic Operations
Node Structure
Each trie node stores a dictionary mapping characters to child nodes and a boolean flag marking whether this node represents the end of a complete word. The children dictionary typically uses hash tables for O(1) character lookup, though arrays indexed by character code can be faster for limited character sets like lowercase English letters.
Insert
Inserting a word involves traversing the trie character by character, creating new nodes as needed for characters that do not yet exist in the tree. The final node is marked as an end of word. Time complexity is O(m) where m is the word length, independent of the total number of strings stored in the trie. This means that even with millions of strings in the trie, inserting a word of length 10 always requires exactly 10 node traversals.
Search
Search follows the same path as insertion but checks whether each character exists in the children dictionary. If any character is missing, the word is not in the trie. If all characters are found, the final node must be marked as end of word for a successful exact match. Time complexity is O(m). This predictable performance makes tries suitable for latency-sensitive applications like autocomplete where response time must remain consistent regardless of dictionary size.
Prefix Search and Prefix Walk
The startsWith operation checks whether a prefix exists in the trie, following the same path as insertion but not requiring the final node to be marked as end of word. The prefix walk operation finds all complete words sharing a given prefix by navigating to the prefix’s node and performing a DFS traversal of all descendant nodes that are marked as end of word. This is the core operation that powers autocomplete functionality.
Use Cases
Autocomplete
Autocomplete is the most common trie application. As the user types each character, the system navigates deeper into the trie and retrieves all complete words from the current node’s subtree. A frequency-aware trie stores a count at each end-of-word node, allowing the system to return completions sorted by popularity. This is how search engines, code editors, and smartphone keyboards provide instant suggestions.
The user experience of autocomplete depends critically on speed. Studies have shown that autocomplete suggestions must appear within 100 milliseconds to feel instantaneous, and trie-based lookup at O(m) time with m being the few characters typed easily meets this requirement even for dictionaries with hundreds of thousands of entries.
Spell Checker
Spell checkers build a trie from a dictionary of valid words. For an input word, the system searches the trie for exact match. If not found, fuzzy search algorithms using Levenshtein distance — the minimum number of single-character edits needed to transform one word into another — explore the trie to find the closest valid words. A Levenshtein automaton constructed on the trie efficiently prunes the search space, exploring only paths that could yield a word within the allowed edit distance.
Modern spell checkers combine multiple strategies. A trie provides the base dictionary for exact matches and prefix-based correction suggestions. N-gram models capture context to suggest words that fit the surrounding text. Personal dictionaries capture user-specific vocabulary like names and technical terms. The trie serves as the backbone, providing the fast lookup that all other strategies depend on.
IP Routing
Network routers use tries for longest prefix matching. IP prefixes are stored in the trie, and when a packet arrives with a destination IP, the router traverses the trie following the IP bits, remembering the longest matched prefix encountered along the path. This determines the most specific route for forwarding the packet. Patricia tries (compressed binary tries) are the standard implementation in routing tables because they minimize the number of memory accesses required for each lookup.
Compressed Trie
A standard trie can have long chains of single-child nodes that waste space and traversal time. A compressed trie merges these chains into single nodes storing multiple characters, reducing node count and memory usage. The trade-off is more complex insertion and deletion logic, since splitting a node may be required when a new word partially matches an existing compressed edge. For production use, standard tries are recommended unless benchmarks show that compression addresses a specific memory constraint.
Time and Space Complexity
Insert, search, and delete are all O(m) where m is the key length. Prefix search is O(m + k) where k is the number of matching results. Space complexity is O(total characters stored) across all strings, with shared prefixes occupying only one set of nodes. For example, storing “cat,” “car,” and “card” creates the shared branch c-a with children t, r, and r-d, using fewer nodes than a hash table would require.
Trie Optimization Techniques
Several optimizations improve trie performance in production applications. Array-based children rather than hash-map-based children eliminate pointer overhead and improve cache locality for small alphabets, though they waste memory for sparse nodes. Ternary search trees combine aspects of tries and BSTs by storing three child pointers per node for less-than, equal-to, and greater-than comparisons, reducing memory usage for non-uniform key distributions.
Backtracking with pruning improves fuzzy search performance by exploring the trie depth-first and pruning branches where the minimum possible edit distance already exceeds the threshold. Bitwise tries compress multiple character comparisons into single bit operations, useful for IP routing tables where performance is critical. A 2023 paper from ACM SIGCOMM showed that optimized trie implementations in network routers can perform longest prefix matching in under 50 nanoseconds per lookup.
Trie Versus Hash Table for String Storage
When choosing between a trie and a hash table for storing strings, several factors guide the decision. Hash tables provide faster exact match lookups at O(1) average compared to O(m) for tries. Hash tables are simpler to implement and use less memory for short strings with few shared prefixes. However, tries excel at prefix-based operations that hash tables cannot support at all. For ordered iteration, tries naturally produce keys in sorted order if children are visited alphabetically, while hash tables provide no ordering guarantees.
When to Use a Trie
Use tries when you need prefix-based search for autocomplete or search suggestions, when working with a known set of strings with shared prefixes, or when you need ordered iteration over keys. Do not use tries when you only need exact match lookups — hash tables are simpler and faster — or when keys are very long with few shared prefixes.
Frequently Asked Questions
What is the difference between a trie and a hash table? A trie supports prefix-based search and ordered iteration. A hash table supports only exact match lookups. Tries have O(m) operations based on key length, while hash tables have O(1) average operations.
How does a trie handle autocomplete efficiently? After navigating to the prefix node, a DFS of all descendants finds all completions. With frequency annotations, the system returns completions sorted by popularity.
What is a compressed trie or radix tree? A compressed trie merges single-child chains into single nodes storing multiple characters, reducing memory usage at the cost of more complex implementation.
Can a trie store non-string data? Yes, any data that can be decomposed into a sequence of discrete symbols can be stored in a trie, including DNA sequences, IP addresses, and feature vectors.
When should I use a trie instead of a balanced BST? Use a trie for prefix-based search and when the key alphabet is small. Use a balanced BST for generic ordered data and range queries.