A trie, also called a prefix tree, is a tree-shaped data structure that stores strings character by character, so that every path from the root spells out a prefix and keys sharing a prefix share the same nodes. Among data structures, it is the standard choice when a program must not only find exact keys but also answer prefix questions, such as which stored words begin with a given sequence of letters.
The name comes from the middle of the word retrieval. Its defining property is that lookup time depends on the length of the key, not on the number of keys stored: finding a ten-letter word takes about ten steps whether the trie holds a hundred words or ten million.
How a trie stores and finds keys
A trie starts with an empty root node. Each node holds links to child nodes labeled with characters, and a flag marks whether the path to that node forms a complete key. Inserting the word cat follows or creates the edges c, a and t and then sets the end flag on the last node; inserting car afterward reuses the c and a nodes and adds only one new edge for r.
Searching walks the same way: start at the root, follow the edge for each character, and fail as soon as an edge is missing. If the walk ends on a node with the end flag, the key exists. A prefix query stops after the prefix and then visits the whole subtree below that node, which yields every stored key that begins with the prefix, conveniently in lexicographic order when children are visited in character order.
| Operation | Time complexity | Notes |
|---|---|---|
| Insert | O(m) | m is the key length; may create up to m nodes |
| Exact search | O(m) | Independent of the number of stored keys |
| Prefix check | O(p) | p is the prefix length |
| List keys with a prefix | O(p + k) | k is the total size of the matching output |
| Delete | O(m) | Remove the end flag and prune empty nodes |
These bounds assume that moving from a node to a child takes constant time, which depends on how child links are stored, the main design decision in any trie implementation.
Node representations and memory use
The child storage method decides the balance between speed and memory. With a small alphabet, such as 26 lowercase letters or the 4 DNA bases, a fixed array per node is fast and simple. With a large alphabet, such as full Unicode, a fixed array would waste enormous space, so nodes store only the children they actually have.
| Representation | Child lookup | Memory use | Best fit |
|---|---|---|---|
| Fixed array | Constant, very fast | High, mostly empty slots | Small alphabets |
| Hash map per node | Expected constant | Moderate, with overhead | Large or unpredictable alphabets |
| Sorted list or array | Logarithmic or linear | Low | Few children per node |
| Ternary search tree | Logarithmic in alphabet | Low | Memory-sensitive string sets |
| Bitmap with packed children | Constant with bit counting | Low | High-performance implementations |
A plain trie can use many times more memory than the raw strings it holds, because each character may become a separate node with pointers. This overhead is the main reason compressed variants exist.
Compressed tries and other variants
Several variants keep the prefix-sharing idea while reducing node count and memory. They differ in how they collapse chains, what they store on edges and which queries they optimize.
| Variant | Key idea | Typical use |
|---|---|---|
| Radix tree | Merges single-child chains into one edge labeled with a string | Routing tables, in-memory key indexes |
| Patricia trie | Binary radix tree that skips identical bits | IP address lookup |
| Suffix tree | Trie of all suffixes of a text, compressed | Substring search and bioinformatics |
| Double-array trie | Encodes transitions in two flat arrays | Fast dictionaries in text processing |
| Finite-state transducer | Shares both prefixes and suffixes, stores values | Compact search engine term dictionaries |
The radix tree is the most widely used refinement: instead of one node per character, an edge may carry a whole substring such as tion, so a dictionary of long words needs far fewer nodes.
Trie compared with other lookup structures
A trie competes with the hash table and the binary search tree for storing sets and maps of strings. The decisive question is whether the application needs ordered or prefix-based queries; if it needs only exact lookups, a hash table is usually simpler and smaller.
| Structure | Exact lookup | Prefix search | Memory | Ordered traversal |
|---|---|---|---|---|
| Trie | O(m) | Native and efficient | High unless compressed | Yes |
| Hash table | Expected O(m) for hashing | Not supported | Moderate | No |
| Balanced binary search tree | O(m log n) comparisons | Possible through range scans | Moderate | Yes |
| Sorted array | O(m log n) with binary search | Range of matches | Low | Yes |
| Bloom filter | Probabilistic membership only | Not supported | Very low | No |
In practice, a sorted array with binary search is a strong, compact alternative for static word lists, while a trie shines when keys change often and prefix queries are frequent.
Applications and practical pitfalls
Tries appear wherever software works with prefixes of keys. Typical applications include autocomplete in search boxes and code editors, spell checkers, word games, longest-prefix matching in network routers and tokenizers that split text into known vocabulary pieces.
- Unbounded memory growth can occur when untrusted input is inserted; cap the key length and the total node count.
- Character encoding must be decided early: storing UTF-8 bytes and storing Unicode code points produce different tries.
- Pointer-heavy nodes cause poor cache locality; flat array layouts are often much faster.
- Forgetting the end-of-key flag makes prefixes such as ca appear to be stored words.
- Recursive deletion must prune only nodes that have no children and no end flag.
Explained without jargon
A trie works like the index tabs of a printed dictionary taken to the extreme. To find a word, you pick the first letter, then the second letter within that group, then the third, and so on. Words that start the same way share the same path.
This makes it very quick to answer a question such as which words start with tra. You walk down three steps and everything below that point is the answer. The cost is that storing every letter as its own stop can take considerable memory.
A typical use case
An online pharmacy wants its search box to suggest product names as customers type. The catalog contains about 40,000 product names, and suggestions must appear in a few milliseconds on every keystroke.
The development team loads the names into a radix tree at startup and stores, in each node, the five most popular products in its subtree. When a customer types ibu, the service walks three characters and immediately returns the stored suggestions without scanning the catalog. Memory use stays modest thanks to the compression, and suggestion latency stays well under the target even during peak traffic, while catalog updates simply insert or remove the affected names.