Radix Tree

A trie with its single-child chains collapsed. Each edge carries a whole substring instead of one character, so the same keys live in far fewer nodes.

Search: O(m)

Space: O(n)

Path compression

Fewer cache misses

Words (comma-separated)

Speed: 1000ms

Step 1 of 00 nodes

Tree — teal edges carry more than one character

just mergedon search pathword ends here

Current Step

Click Play to begin

Complexity

Search:O(m)

Insert:O(m)

Space:O(n)

Nodes vs trie:far fewer

m = key length, n = total characters stored

Key Concepts

Merge rule: one child and no word ending
Same keys, fewer nodes and fewer pointers
Cost: inserts may have to split an edge again
Used in IP routing tables and key-value stores

Compare with the uncompressed trie →

Knowledge Check

Question 1 of 3

What exactly does a radix tree compress compared with a plain trie?

Indexing

Hashing your keys…

DSAverse

Radix Tree

Tree — teal edges carry more than one character

Current Step

Complexity

Key Concepts

Knowledge Check

Radix Tree

Tree — teal edges carry more than one character

Current Step

Complexity

Key Concepts

Knowledge Check