A trie (prefix tree) stores one character per edge, so words sharing a prefix share a path — insertion, search and prefix lookup all run in O(|query|) time, independent of how many words are stored. Its weakness is memory: a long unbranching chain of characters still costs one node per character.
A radix trie (also called a PATRICIA trie or compressed trie) fixes this by merging every node that has exactly one child and is not itself a word ending into its parent edge, so a chain of single-character edges becomes one edge labelled with the whole substring:
compress(node):
for each child c of node:
label = edge(node, c)
while c is not a word AND c has exactly 1 child:
label += edge(c, c's only child)
c = c's only child
emit compressed edge "label" -> compress(c)
This guarantees a hard bound: a radix trie built from n distinct keys has at most 2n − 1 nodes, no matter how long the keys are — because every internal node left standing has ≥ 2 children or is a word ending, so the branching structure alone bounds the count. Lookup cost stays O(|query|) — you just compare against longer substrings per step instead of one character.
- Compress to Radix Trie — rebuilds the same word set as a PATRICIA trie; watch the single-child chains disappear into merged edges and the node count drop.
- Prefix query — walks the currently displayed tree edge by edge, consuming as much of your query as each edge label matches, and highlights the path plus every word reachable from where it stops — exactly how a real autocomplete index turns a keystroke into a suggestion list.
Real-world relevance: compressed radix/PATRICIA tries back IP routing tables (Linux's fib_trie), and are the standard structure behind fast prefix-based autocomplete and spell-check indexes where memory, not just speed, matters.