Tries (Prefix Trees)

The 10-second versionCopy Anchor Link

Every tree so far compares whole keys to decide where to go. A trie (say "try") throws that away: it stores strings one character per edge, so a key isn't a value sitting in a node — it's the path you take from the root. Walk c → a → t and you've spellt cat. That one decision changes the game. Strings that share a beginning — car, cart, cat — share the same path for as long as they agree, so prefixes are shared for free, and a lookup costs O(length of the key) no matter how many keys are stored. Exact-match is fast; more importantly, "what starts with this prefix?" — the question a hash table can't even hear — is a single descent followed by a quick scan of the subtree.

Why this existedCopy Anchor Link

Imagine you're building a dictionary for autocomplete. You need to answer two questions, constantly:

1. Is the exact word apple present?
2. Which words begin with app?

A hash table nails question 1 in O(1) — but it destroys the very structure that question 2 is about. app, apple, and apply scatter to unrelated buckets, because hashing deliberately scrambles a key into a uniform blob. To answer "starts with," you'd have to hash every candidate word — back to a linear scan. And a sorted array can find the range of app... with binary search, but it still copies and stores each key in full, re-reading shared prefixes over and over.

The waste is real even before the query: apple, apples, apply, applied all re-encode appl from scratch, in every single key, in every structure that stores whole words.

The idea that fixes this is old. In 1959, René de la Briandais described a tree-shaped structure for searching files, where each level broke on one character of the key. In 1960, Edward Fredkin gave it the name it stuck with: trie, pulled out of the middle of reTRIEval — and pronounced "try" on purpose, so you'd never confuse it with a plain old "tree." In 1968, Donald R. Morrison compressed the structure into the PATRICIA trie (Practical Algorithm To Retrieve Information Coded in Alphanumeric), collapsing long single-child chains into single edges — a fix for the space cost you'll meet below.

Why it mattered then: it was the first structure where a key's characters, not its comparisons, did the navigating — and that made prefix queries a primitive instead of a burden.

Inside the inventor's headCopy Anchor Link

The problem, stated cleanly, is autocomplete. You have a big set of words; you want, given app, the whole list of completions. What's the natural operation? "Find the subtree of everything that begins with app." But no data structure you have has such a thing: arrays and hash tables are flat; there's no "the part that starts with app."

Here's the trap everyone falls into first. You keep a plain list of words and, for every keystroke, filter the whole list:

// Naive: check every stored word, every query — O(words × prefix length).function suggest(words, prefix) {  return words.filter((w) => w.startsWith(prefix));}

That's O(number of words) per keystroke. For a real dictionary that's millions of comparisons per character typed — hopeless.

The pivot is to stop thinking of the key as something you store, and start thinking of it as something you trace. Picture each character as a labeled edge:

Watch what that buys. The moment max and maximum share their first three letters, they share the same three edges — one copy of max, not two. The prefix is the path, so "find everything starting with max" is literally "find the node at the end of the max path, then gather what hangs below it." A hash table threw that path away; the trie makes it the whole point.

// Improved: one descent of the prefix — O(prefix length), independent of dictionary size.function walk(node, prefix) {  for (const ch of prefix) {    if (!node) return null;    node = node.children.get(ch);  }  return node;                    // the node where the prefix ends, or null}

The final approachCopy Anchor Link

The shapeCopy Anchor Link

Insert cat, car, cart, dog. Notice how car and cat share ca, and how cart simply continues car by one more edge. A ✓ marks a node where a complete key ends:

The marked-but-not-terminal distinction is the subtle bit: after inserting these four words, the node for ca exists, but it is not a word — nothing ends there. car and cart both exist, and one is a prefix of the other; only the marks tell them apart.

The algorithm, as a flowCopy Anchor Link

Lookup is the same walk for contains and for startsWith; the only difference is what you require at the end:

The invariants that make it correctCopy Anchor Link

1. The root stands for the empty string. Every key is a path starting there.
2. Each edge is exactly one character. Walking a path from the root reads out a string, character by character.
3. A key is present iff its path exists and the node at the end is marked terminal. Merely passing through a node proves nothing — that's how car and cart coexist.
4. Keys with a common prefix share their shared path. There is exactly one node per distinct prefix, which is where the sharing (and the space savings) comes from.
5. All descendants of a node share that node's prefix. This is what makes "the subtree under the app node" exactly the set of completions.

A worked traceCopy Anchor Link

Insert cat, car, cart, dog into an empty trie:

• c → a → t: the path is created as we go, and the t node is marked terminal (cat).
• car: walk c, a (they already exist — shared, no new nodes), then add r and mark it (car).
• cart: walk c, a, r (all shared), then add t and mark it (cart). The r node is both a word-end and a stepping stone.
• dog: nothing is shared, so a fresh branch d → o → g is created and g is marked.

Now startsWith("ca") walks two edges and returns the a node — non-null means the prefix exists. contains("ca") walks the same two edges but returns false, because the a node is not terminal. And collecting ca's subtree yields cat, car, cart — the whole completion list, in O(prefix + output).

It in codeCopy Anchor Link

A complete trie: insert, exact contains, prefix startsWith, and a DFS collector.

class Node {  constructor() { this.children = new Map(); this.terminal = false; }}function insert(root, key) {  let n = root;  for (const ch of key) {    if (!n.children.has(ch)) n.children.set(ch, new Node());   // create the edge if new    n = n.children.get(ch);  }  n.terminal = true;                          // mark the end of a key}function contains(root, key) {  let n = root;  for (const ch of key) {    n = n.children.get(ch);    if (!n) return false;                     // the path broke → absent  }  return n.terminal;                          // must END here, not merely pass through}function startsWith(root, prefix) {  let n = root;  for (const ch of prefix) {    n = n.children.get(ch);    if (!n) return false;  }  return true;                                // the prefix is a path (not necessarily a word)}function collect(n, prefix = "", out = []) {  // list every key under this node  if (n.terminal) out.push(prefix);  for (const [ch, child] of n.children) collect(child, prefix + ch, out);  return out;}

Cost tableCopy Anchor Link

L is the length of the key or prefix; n is the number of keys stored; Σ is the alphabet size.

The time column is the magic: lookups are O(L), independent of how many keys you store. Compare that to a hash table's O(1) average (also independent of n, but blind to prefixes) or a sorted array's O(L log n).

The space is the catch, and it's what the compressed variants exist for. A plain trie wastes pointers on children that don't exist, and it stores long, unbranching chains one character at a time — a single key like antidisestablishmentarianism creates 28 nodes in a row. A radix trie (or Patricia trie) collapses each such chain into a single edge that carries the whole substring, so every internal node branches and the node count is proportional to the number of keys, not their total length.

Where you meet it todayCopy Anchor Link

• Autocomplete everywhere. The suggestion box as you type is a startsWith descent followed by a subtree walk — which is why it can offer completions after every keystroke instead of re-scanning a word list.
• Spell-checking and fuzzy search. A dictionary trie plus a bounded edit-distance walk prunes whole subtrees the moment the prefix alone exceeds the allowed number of edits.
• IP routing. Internet routers perform longest-prefix match: the routing table is a binary trie (one bit per edge), and forwarding is a walk that keeps the last matching prefix it saw. The Patricia trie makes this compact enough for millions of routes.
• T9 and predictive keyboards. A trie over the dictionary turns a sequence of digits into the words that could spell it — prefix lookup again.

// Walk the prefix once, then list everything hanging below it.let start = root;for (const ch of "ca") if (start) start = start.children.get(ch);if (start) console.log(collect(start, "ca"));   // ["car", "cart", "cat"]

RecapCopy Anchor Link

• A trie stores keys one character per edge; a key is a path from the root, not a value in a node.
• Exact contains and prefix startsWith both cost O(L) — key length, independent of how many keys you store.
• Shared prefixes share their path, so car, cart, cat don't duplicate ca.
• The terminal mark is essential: car being a word and cart being a word means passing through a node proves nothing.
• The space cost is the price — which is why radix and Patricia tries collapse long single-child chains into fat edges.

Next up: Graph Representations — a tree is a special graph, and it's time to let edges go anywhere.