A trie, pronounced "try," from retrieval, is a tree that stores strings one character at a time, where every path from the root spells out a prefix, and nodes along a shared prefix are shared between every word that starts with it. That structure makes prefix operations — give me every word starting with "pre" — genuinely fast, in a way neither a hash map nor a sorted array can match without extra work. It is the structure quietly running underneath autocomplete boxes, spell checkers, and IP routing tables.
What changed in 2026
- Tries kept their niche as the right answer for prefix search, even as general-purpose search moved toward embeddings and approximate nearest-neighbor indexes for fuzzier matching.
- Compressed variants, radix trees or Patricia tries, became the default in serious implementations. Collapsing chains of single-child nodes into one edge cuts memory dramatically, which matters because plain tries are memory-hungry.
- Tries continued to anchor IP routing and DNS lookups, where matching the longest known prefix is exactly the operation a trie is built for.
The node structure
Node:
children: map of character -> Node (often a fixed-size array for a-z)
isEndOfWord: boolean
Inserting "cat" and "car" produces a shared path for c then a, which then splits into two branches, t and r, each marked as end of word.
c
|
a
/ \
t r
(cat) (car)
Core operations
- Insert: walk the string character by character, creating a child node whenever one does not already exist, and mark the final node as end of word. O(m), where m is the string length.
- Search, exact match: walk the string the same way; falling off the tree, or landing on a node not marked end of word, means the word is not present. O(m).
- Prefix search: walk to the node representing the prefix, then collect every end-of-word node in the subtree beneath it. O(m + k), where k is the number of matches.
Trie operations depend on string length, not on how many words are stored — a trie with a million entries is not slower to search than one with a hundred, as long as the query string length is the same.
Trie vs the alternatives
| Structure |
Exact search |
Prefix search |
Memory |
Sorted iteration |
| Hash map |
O(m) average |
O(n·m), must scan |
High |
No |
| Sorted array of strings |
O(m log n) |
O(m log n) plus scan |
Low |
Yes |
| Trie |
O(m) |
O(m + k) |
High, plain, lower compressed |
Yes |
| Binary search tree of strings |
O(m log n) |
Poor, no native prefix support |
Medium |
Yes |
Where tries actually get used
- Autocomplete and search-as-you-type, where every keystroke needs all words starting with what has been typed so far, fast enough to feel instant.
- Spell checkers, walking a trie of the dictionary and allowing small edit-distance deviations at each step.
- IP routing tables, where routers match the longest known prefix of a destination address — a direct application of trie prefix search over binary strings.
- T9 and predictive text, mapping key sequences to candidate words via a trie built over the vocabulary.
Common pitfalls
Using a plain trie for a small dataset. The per-character node overhead is real; for a few hundred short strings, a hash map or even a linear scan is simpler and not meaningfully slower.
Forgetting the end-of-word marker. Without it, there is no way to distinguish a path that exists only because a longer word was inserted from the shorter word itself being present — prefix and exact match get conflated.
Not compressing single-child chains. A plain trie over long, rarely-branching strings, such as URLs or file paths, wastes enormous memory on one-child-per-node chains; a radix tree collapses these into single edges.
FAQ
Is a trie the same as a binary search tree?
No. A BST branches on value comparisons, less than or greater than, and holds one full value per node. A trie branches on individual characters and only represents a complete value once a path reaches an end-of-word node.
How is a trie different from a hash map for storing strings?
A hash map gives O(1) average exact lookup but no efficient way to find all keys sharing a prefix. A trie trades slightly slower exact lookup for genuinely fast prefix queries.
What is a radix tree, and how is it different from a trie?
A radix tree, or Patricia trie, is a compressed trie — chains of nodes with only one child are merged into a single edge holding a substring, cutting memory use substantially while keeping the same prefix-search behavior.
Do tries only work for text?
No — anything expressible as a fixed-alphabet sequence works, including binary representations of IP addresses or numbers, which is exactly how routing tables use them.
Where to go next