What does a radix trie save compared to a standard trie?
A standard trie stores one character per node; a radix trie collapses single-child chains into multi-character edges. For 'car', 'card', 'care', 'cart', a standard trie uses 7 nodes; a radix trie uses 2 ('car' + 'e'/'t'/'d'). Savings: 60-70% of memory for long prefixes.
Answered in
Tries: Why Autocomplete Doesn't Scan Every WordA trie finds all words with a prefix in O(p) time, independent of dictionary size. Radix compression and top-k heaps make autocomplete instant.
Read the full analysisOther questions this article answers
More system design questions
- Why doesn't Google just run Dijkstra faster?
- What is a shortcut edge and when is it precomputed?
- How much space do shortcut edges take compared to the original graph?
- Can Contraction Hierarchies handle dynamic graphs like traffic or road closure?
- Why contract low-degree nodes first instead of high-degree ones?
- What is a CRDT and why does it matter for real-time collaboration?
- How do CRDTs handle concurrent edits without a central server referee?
- Why did Figma move from operational transforms to CRDTs?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.