Trie

What is a trie

A trie is a tree that stores keys by spelling them. Each edge stands for one character, so a key is not kept in any single node: it is the path from the root down to where it ends. Keys that start the same way share the start of their path, which is why the structure is also called a prefix tree. Both names mean the same thing.

The name comes from retrieval. Most people pronounce it "try", to keep it apart from "tree", although it is one.

Every node holds one letter, the one on the edge that leads into it, and the label under a node is the word whose path ends there. Reading down from the root through c, a and r spells car; one more step spells cart. Nothing in the trie compares one key against another. A key's position follows from its letters alone.

The problem the earlier structures couldn't solve

The hash table answers "is cart here?" in expected O(1) probes. Ask it which stored keys start with ca and it has nothing to offer: the hash of cart says nothing about the hash of car, so the keys sharing a prefix are scattered across the buckets on purpose. The only way to answer is to read every key.

A Binary Search Tree keeps the keys sorted, so everything starting with ca sits in one contiguous range and a range query finds it. But every step down the tree compares two whole keys. With n keys of length k, a lookup makes O(log n) comparisons and each one may read up to k characters, even though the first few characters were already settled by the comparisons above it.

A trie reads each character of the key once, and the number of keys stored doesn't enter the cost at all.

Search, startsWith and insert

All three operations are the same walk. Start at the root, and for each character of the key follow the child for that character.

Search

To look up cart, follow c, a, r and t. Four letters, four steps, whether the trie holds five words or five million.

The walk fails as soon as a letter has no child. Searching for cow stops at c, which has no o child, after a single step.

The end-of-word marker

Searching for ca follows c and a successfully, and ca is still not a stored word. Reaching a node only proves that some stored word starts with that prefix. So each node carries one more bit, an end marker, set when a key ends exactly there.

The marker is what lets car and cart share a path. car ends at the r node and cart continues one level below it, and both are stored because both nodes carry the marker. Without it the trie could only store keys where no key is a prefix of another.

startsWith

startsWith is the same walk with the end marker ignored: if the walk reaches the end of the prefix, at least one stored key starts with it. Collecting those keys means visiting the subtree under that node, and every node in it is a match.

Reaching the prefix costs O(k). Listing what is under it costs one visit per node in that subtree, which is the size of the answer itself. Children are visited in letter order, so the words come out sorted.

Insert

Insert walks the key the same way, and wherever a letter has no child it creates one. Then it sets the end marker on the last node.

Inserting care reuses c, a and r and creates only the e. Inserting a word that is already a prefix, like ca, creates nothing at all: the nodes exist, and only the marker changes.

Deletion

Deleting a key clears its end marker. That alone is enough for search to stop finding it, but it can leave nodes behind that no key uses any more. Those get pruned: on the way back up, any node with no end marker and no children is freed, and pruning stops at the first node another key still needs.

Deleting cart frees the t under car and stops there, because car carries an end marker. Deleting car afterwards frees the r node, which by then has no children and no marker, and stops at ca, which still leads to cat.

Delete car while cart is still stored, and nothing is pruned. The r node keeps its place with the marker cleared, because cart passes through it.

Representing a trie in memory

The simplest node gives every letter its own slot: an array of 26 child pointers for lowercase English, plus the end marker. Finding a child is one index, children[c - 'a'], with no search.

Search, StartsWith and Insert are one loop over the key's bytes. Delete recurses so it can prune on the way back up, and it reports whether the key was stored. This version only accepts 'a' to 'z'; any other byte indexes outside the array and panics.

What a node costs

The array makes child lookup a single index, and it pays for that in space: every node carries 26 pointers whether it uses them or not. Below the first couple of levels most nodes have one child, so most of the trie is nil pointers. Indexing on raw bytes, to accept any key, makes each node ten times larger.

A map per node stores only the children that exist, which pays off when the alphabet is large and the nodes are sparse, as with bytes or Unicode. It gives up the single-index lookup: each step hashes the character and probes. Some implementations sit in between, with a short sorted slice of (char, child) pairs per node, searched linearly because it rarely holds more than a few entries.

Try it yourself

The playground runs the code above on the trie from the first figure. Search ca to see a path that exists without being a word, then try Starts with on it. Insert care and only one node appears; delete cart and one node is pruned, while deleting car with cart still stored prunes nothing.

Compressed tries and radix trees

Long keys make long chains: a path where each node has one child and no end marker stores one letter per allocation and decides nothing. A compressed trie, usually called a radix tree (or Patricia trie in its binary form), merges every such chain into a single node labelled with the whole string.

The words and the answers are the same; only the chains are gone. A node now exists only where keys branch or end, so the node count is bounded by the number of keys instead of the number of letters. The walk changes in one way: at each node it compares a run of characters against the label instead of a single one, and an insert that diverges in the middle of a label splits that node in two.

Common operations and their costs

k is the length of the key, n the number of keys stored, m the number of matches a prefix query returns.

On single-key lookups the trie and the hash table land in the same class, because the hash table has to read the whole key to hash it. The difference is in the prefix row: the trie is the only one of the three whose cost depends on the answer instead of on everything stored.

Tries in the real world

Autocomplete. Typing ca into a search box is a startsWith query: walk to the ca node and list what is under it. Near the root that subtree can hold most of the dictionary, so a common refinement stores a weight on each end-marked node (how often the term was searched) and keeps the few heaviest completions cached on each node, which turns a keystroke into a walk plus a read.

Spell checking. Checking a word against a dictionary is a search. Suggesting corrections means exploring paths that differ from the typed word by a letter or two, and a trie lets the search drop a whole branch as soon as its prefix is already too far from the input.

IP routing. A router forwards a packet by the longest prefix match: among all the network prefixes in its table (10.0.0.0/8, 10.1.0.0/16), it picks the longest one that matches the destination address. That is a walk down a trie over the address's bits, remembering the last node that carried a route. The Linux kernel's IPv4 routing table is an LC-trie, a binary trie that uses level compression to replace runs of binary nodes with wider ones.

HTTP routers in Go. httprouter matches request paths with "a compact prefix tree (or just Radix tree)", in its own words; gin uses a custom version of httprouter, and chi and echo describe their routers as radix trees too. The standard library's ServeMux, since Go 1.22, matches patterns with a decision tree that branches on the host, then the method, then each segment of the path, which makes it a trie whose "characters" are path segments.

When tries fall short

Memory per node. Every letter of every key that doesn't share a prefix becomes an allocation of its own, mostly made of empty pointers. A hash set stores each key's bytes once, so for "is this key here" alone it takes far less memory.

Pointer chasing. Each step of the walk loads a child pointer and then the node it points at, which sits in its own allocation somewhere else in memory. A long key means a chain of dependent memory accesses, each a likely cache miss on a large trie, where a hash lookup hashes the key and touches one or two cache lines.

Keys have to be sequences. The trie needs keys that break into a sequence of small symbols, such as characters, bytes, bits or path segments. Floating-point numbers or composite records have no useful character-by-character structure to share.

A fixed alphabet or a slower step. The array node assumes a small known alphabet. Supporting arbitrary bytes or Unicode means either a 256-wide node with ten times the memory, or a map or slice per node and a lookup that is no longer one index.

Summary

• A key is a path: each edge is a character, keys that share a prefix share the start of their path, hence "prefix tree"
• The cost depends on the key length, not on how many keys are stored
• The end marker tells a stored key apart from a prefix of one, which is what lets car and cart both be stored
• Deletion clears the marker and prunes the nodes no other key uses, stopping at the first one that is still needed
• A 26-slot node is one index per step and mostly empty pointers; a map per node saves memory on large, sparse alphabets
• A radix tree merges single-child chains into one node, so the node count follows the number of keys instead of the number of letters
• Prefix queries are the reason to use one: autocomplete, longest prefix match in routing tables, HTTP routers. For exact lookups alone a hash set is smaller and usually faster