↩ back to Node-Linked Trees

Radix Tree (PATRICIA Trie)

A trie spends one node per character — "cat" and "car" share a c → a path, but every single character still gets its own node, even along a stretch where only one path forward ever exists. A radix tree (also called a PATRICIA trie, for "Practical Algorithm To Retrieve Information Coded In Alphanumeric") fixes exactly that waste: any chain of nodes that each have exactly one child gets collapsed into a single edge labeled with the whole shared substring, not one character. Walking the tree still costs one step per branch point, not one step per character — for a set of keys with long unbranching runs, that can be far fewer edges than characters.

Try it

The tree below is preloaded with the classic seven-word PATRICIA example: romane, romanus, romulus, rubens, ruber, rubicon, rubicundus. Every edge is labeled with the actual substring it represents — notice there's a single edge labeled "om" under the root's "r" edge, not two separate one-character edges for o then m, because nothing else ever branches off partway through "om". The small dot on a node marks it as a real stored word, same convention as the Trie page. Insert adds a word (new or split nodes get a thick border), Search checks whether an exact word is stored, Prefix lists every stored word starting with what you typed, and Delete removes a word — watch how a deletion can merge two edges back into one, not just prune a leaf.

Core operations

• insert(word) — walk from the root; at each node, look at the child edge whose first character matches. If there's no such edge, add a brand-new one labeled with the entire remaining suffix — done in one step, no per-character nodes at all. If an edge exists, compare it against the remaining suffix character by character to find how much they share. If the whole edge label matches, continue into its child and keep walking. If only part of it matches, split the edge at that point: insert a new node at the split, keep the unmatched tail of the old edge hanging off it, and add a second new edge for whatever's left of the word being inserted (or just mark the split node itself as a stored word, if nothing's left).
• search(word) — the same walk, but it only counts as found if it lands exactly on a node boundary with that node's isEnd flag set. Stopping partway through a compressed edge is never a match, even if the edge's far end happens to be a stored word — see Pitfalls.
• startsWith(prefix) / collect — same walk, but succeeding partway through an edge is perfectly fine (a prefix doesn't need to land on a boundary). The demo collects every complete word in the subtree from wherever the prefix walk ends, same as the Trie page's autocomplete list.
• delete(word) — walk to the word's node and clear its isEnd flag. Then walk back up: if the node just below the current edge now has zero children and isn't itself a stored word, remove the edge entirely and keep walking up. If it has exactly one remaining child and isn't a stored word, merge — splice that single child's edge label onto the end of the current edge and stop, since the parent's own child count didn't change. Anything else (two or more children, or still a stored word) means the node is still needed as-is; stop immediately.

Reference implementation

function commonPrefixLen(a, b) {
  let i = 0;
  const m = Math.min(a.length, b.length);
  while (i < m && a[i] === b[i]) i++;
  return i;
}

function insert(root, word) {
  let node = root, i = 0;
  while (i < word.length) {
    const ch = word[i];
    const edge = node.children.get(ch);
    if (!edge) {
      node.children.set(ch, { label: word.slice(i), child: makeNode(true) });
      return;
    }
    const rem = word.slice(i);
    const cpl = commonPrefixLen(edge.label, rem);
    if (cpl === edge.label.length) {
      node = edge.child;
      i += cpl;
      if (i === word.length) node.isEnd = true;
      continue;
    }
    const mid = makeNode(false);
    mid.children.set(edge.label[cpl], { label: edge.label.slice(cpl), child: edge.child });
    edge.label = edge.label.slice(0, cpl);
    edge.child = mid;
    i += cpl;
    if (i === word.length) mid.isEnd = true;
    else mid.children.set(rem[cpl], { label: rem.slice(cpl), child: makeNode(true) });
    return;
  }
}

function deleteWord(root, word) {
  const path = []; // { parent, ch, edge }
  let node = root, i = 0;
  while (i < word.length) {
    const edge = node.children.get(word[i]);
    if (!edge) return false;
    const rem = word.slice(i);
    const cpl = commonPrefixLen(edge.label, rem);
    if (cpl !== edge.label.length) return false;
    path.push({ parent: node, ch: word[i], edge });
    node = edge.child;
    i += cpl;
  }
  if (!node.isEnd) return false;
  node.isEnd = false;
  let keepGoing = true;
  for (let k = path.length - 1; k >= 0 && keepGoing; k--) {
    const { parent, ch, edge } = path[k];
    const child = edge.child;
    if (child.children.size === 0 && !child.isEnd) {
      parent.children.delete(ch);
      keepGoing = true;
    } else if (child.children.size === 1 && !child.isEnd) {
      const [, onlyEdge] = [...child.children.entries()][0];
      edge.label += onlyEdge.label;
      edge.child = onlyEdge.child;
      keepGoing = false;
    } else {
      keepGoing = false;
    }
  }
  return true;
}

The split step in insert is the one piece with no equivalent in a plain trie: an existing edge can get cut in two, with a brand-new branch node inserted at the cut, whenever a new word agrees with it for a while and then diverges (or ends). Verified from scratch against a plain-array oracle (search checked against includes, prefix checked against a linear filter by prefix) with three separate passes: an exhaustive sweep of all 64 subsets of a 6-word set chosen for heavy prefix overlap (insert each subset, check every word plus every non-member, delete the whole subset back out, confirm the tree returns to exactly one node — the empty root — every time); an exhaustive sweep of all 720 insertion orders (permutations) of that same 6-word set, confirming search/prefix/collect results never depend on which order the words arrived in; and 45,000 randomized interleaved insert/search/prefix/delete trials across three alphabet sizes (2, 8, and 26 symbols, to force heavy, moderate, and sparse prefix sharing respectively), checking agreement with the oracle after every single operation — zero mismatches across all three passes. A structural invariant (no non-root, non-word node may have exactly one child — if it does, compression has a bug) was also checked after every operation in the randomized pass, with zero violations. Rebuilding the classic seven-word example above and comparing node counts confirms the compression claim directly rather than just asserting it: this exact word set costs 14 nodes as a radix tree versus 28 as a plain trie — exactly half, for this particular set. The real shipped insertRadix/searchRadix/prefixRadix/deleteRadix functions below were then re-verified the same way (10,000 more randomized trials against the same oracle, zero mismatches) and separately driven through their actual click handlers with a fake-DOM harness, replaying a fixed sequence of operations against the preloaded tree and confirming every log line and rendered edge label match exactly.

Pitfalls

"The walk didn't hit a dead end" is not the same as "found." Because an edge now represents several characters at once, a query can walk correctly through every character it has and still stop partway through a compressed edge — nowhere near a real node boundary. A search that forgets to check for this and just tests whatever node the walk last touched will report false positives whenever that node happens to be a real word further down the same edge. Concretely, on the demo's own preloaded tree: querying "ruben" (not a stored word — "rubens" is) walks correctly through r → ub → e and then only one more character, n, into the two-character edge "ns" leading to "rubens." A boundary-blind search that skips the "did I actually reach a real node" check reports "ruben" as found anyway, because the node at the far end of that edge (reached by continuing to "rubens") is a real word. A sweep of every strict-prefix truncation of all seven demo words (dropping the last 1 through k−1 characters) found this boundary-blind version reports 10 of 41 such truncated, never-inserted queries as falsely "found."

Delete has to merge, not just prune — otherwise compression erodes back to a plain trie, one deletion at a time. Removing a dead leaf is the easy half; the part that's easy to skip is checking whether the leaf's parent just dropped to a single remaining child and needs to be spliced back into its own parent's edge. A version of delete that only ever removes empty leaves — never re-merging — stays structurally valid (search and prefix still give correct answers) but slowly gives back every space saving the tree was built for. Concretely: build one 20-character word plus 19 "side branch" words, each one sharing a successively longer prefix of it and diverging by one extra character at the very end, then delete every side branch, leaving only the original 20-character word. A correct delete collapses the tree back down to 2 nodes — root plus one edge holding the whole word, exactly as if it had been inserted alone. The never-merge version instead leaves 21 nodes: a straight chain of one node per character, the exact shape a plain trie would produce, with none of the compression this structure exists to provide.

Where radix trees show up

• IP routing tables. The Trie page names "longest prefix match" over address bits as a routing use case — real routers and the Linux kernel's own routing table (fib_trie) use exactly this compressed variant, not a plain bit-by-bit trie, because a naive one-node-per-bit trie over the full IPv4/IPv6 address space wastes enormous amounts of memory on long unbranching runs that compression collapses away for free.
• Ethereum's state storage. The "Merkle Patricia Trie" — the name says both halves outright — combines this exact compressed-edge structure with the content-hashing idea from the site's own Merkle Tree page, so any single account balance or contract slot can be proven part of a much larger state root without revealing the rest of it.
• In-memory key-value indexes. Redis's cluster-slot and key-routing internals (the rax library) and several embedded databases use radix trees as a memory-efficient sorted index over string keys, favoring it over a hash table exactly when range/prefix queries matter and over a plain trie exactly when key sets are sparse (few keys sharing any given prefix) and per-node overhead would otherwise dominate.

Complexity

Time: insert, search, and startsWith are all O(k) for a word or prefix of length k, the same bound as a plain trie — but the constant behind that bound is smaller in practice, since each step advances by a whole edge label, not one character. On the demo's own tree, searching "rubicundus" (10 characters) takes exactly 4 edge traversals (r → ub → ic → undus) instead of a trie's 10, one per branch point rather than one per character. Space: proportional to the number of edges, not the total character count — the classic seven-word example above costs 14 nodes as a radix tree against 28 for the same words in a plain trie. Worst case (no two stored words share any prefix at all) degrades to the same O(n · k) bound a trie has in that case too, since there's nothing left to compress.

This site's guide, Choosing a Search Tree, places this entry alongside Trie and Ternary Search Tree as answering the same different question the guide's seven comparison entries don't: storing strings and answering prefix queries by spending nodes on characters, not whole keys. It's the third of three routes to that question — instead of changing what a node costs the way Ternary Search Tree does, it changes how many nodes exist at all, collapsing every run of single-child trie nodes into one edge labeled with the whole shared substring.