Tries: The Prefix Tree Behind Autocomplete

What Is a Trie?

A trie (pronounced 'try', from retrieval) is a tree-shaped data structure built specifically for storing strings. Unlike a binary search tree, where each node holds a whole key, a trie node typically holds a single character, and a complete word is spelled out by following a path of characters from the root down to some marked node. The defining trick is that shared prefixes share structure: if you insert both 'cat' and 'car', the root branches to a child for 'c', that child branches to a child for 'a', and only after that shared 'ca' path does the tree split into separate branches for 't' and 'r'. Every word that begins with 'ca' passes through that exact same pair of nodes. Each node also carries a flag marking whether the path ending there is a complete word on its own, since one word can be a prefix of another (like 'car' and 'card'). This design means the trie's shape is determined entirely by the vocabulary it stores, and any two strings that share a prefix of length k will overlap for exactly k nodes before diverging, no matter how different they become afterward.

Insertion: Building the Tree Character by Character

Inserting a word into a trie is a straightforward walk. Starting at the root, you look at the word's first character and check whether the current node already has a child for it. If it does, you simply move down into that existing child; if it doesn't, you create a brand-new child node for that character and then move into it. You repeat this for every character in the word, extending the path only where it doesn't already exist. Once you've consumed the last character, you mark that final node as the end of a valid word. Because existing shared prefixes are reused rather than duplicated, inserting 'cat' after 'car' costs only one new node (for 't'), since the 'c' and 'a' nodes already exist from the earlier insertion. Insertion runs in time proportional to the length of the word being inserted, not the number of words already stored, which is what makes tries scale gracefully as a dictionary grows. This same character-by-character walk is reused almost unchanged for lookups: searching for a word just checks that each required child exists in sequence and that the final node is flagged as a complete word, failing fast the moment a needed character is missing.

Prefix Search: Why It's Fast

The real payoff of a trie is answering prefix queries like 'find every word starting with pre' without scanning the whole dictionary. The algorithm walks the trie following the prefix's characters, exactly like a search, until it reaches the node representing the last character of the prefix. From that single node, every word underneath it in the subtree begins with that prefix, so collecting all matches is just a depth-first traversal of that subtree, collecting each path that ends at a word-flagged node. Consider a tiny trie built from cat, car, card, care, and dog. Walking 'ca' lands you at the shared node after 'c' then 'a'; the subtree below it contains branches for 't' (cat), 'r' (car, which is itself a complete word), 'rd' (card), and 're' (care) -- four matches found by exploring just that one subtree, never touching the unrelated 'dog' branch at all. The cost of locating the prefix's subtree depends only on the prefix's length, and the cost of listing matches depends only on how many matches and characters they contain, not on the total dictionary size. That's the structural reason prefix search feels instantaneous even over huge vocabularies.

Memory Tradeoffs and Compressed Variants

Tries trade memory for speed, and for sparse data that trade can be a poor one. A plain array of nodes per character (say, 26 slots for lowercase letters) means every node reserves space for all possible next characters even if only one or two are ever used, so a trie holding a small, sparse set of long, dissimilar words can consume noticeably more memory than simply keeping those words in a sorted list or array and binary-searching it. The overhead comes from all the single-child chains: a long word with no siblings still gets one full node per character. Radix trees (also called Patricia tries) address this by collapsing chains of single-child nodes into one edge labeled with a whole substring instead of one character, so a unique suffix like 'ardvark' becomes a single edge rather than seven separate nodes. This keeps prefix-sharing benefits for branching regions while eliminating wasted structure along sparse, non-branching runs. Other implementations swap fixed-size child arrays for hash maps or sorted small arrays per node, trading a bit of per-lookup speed for much lower memory when the alphabet is large (like Unicode) or when most nodes have very few children, which is the common case in real-world dictionaries.

Real-World Uses

Tries and their compressed relatives show up anywhere fast prefix matching matters. Autocomplete and search-suggestion systems use them to instantly list completions as a user types, often storing frequency or popularity data at each word node to rank suggestions. Spell checkers walk a trie to confirm whether a typed word exists in the dictionary and can suggest nearby valid words by exploring branches that differ by only one character. IP routing tables use a specialized trie over binary address prefixes to perform longest-prefix matching, letting routers decide which of many overlapping network rules applies to a packet's destination address by walking bit by bit down the tree and remembering the deepest match found. T9 predictive text, the technology behind typing words using a numeric phone keypad, mapped each key press to a set of possible letters and used trie-like structures to narrow down valid dictionary words as digits were entered, offering the most likely word before typing finished. In each case, the same underlying property is being exploited: because related strings share structure, a single tree walk can answer a whole class of questions about many strings at once.

Frequently asked questions

Try it live

Everything above runs in your browser — open Tries: The Prefix Tree Behind Autocomplete and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.