Back to Technology

Trie Variants: Radix, Patricia & XOR Tries

September 9, 2026 Wasil Zafar 22 min read

The standard hash-map trie is only the beginning. This lesson covers the variants engineers actually reach for: compressed radix trees, Patricia tries for routers, a real binary trie for maximum XOR, and ternary search tries.

Table of Contents

  1. Introduction & Motivation
  2. Prerequisites
  3. Compressed Trie / Radix Tree
  4. Binary Trie for XOR
  5. Ternary Search Trie
  6. Persistent Trie
  7. Complexity Comparison
  8. Applications & Alternatives
  9. Exercises
  10. Summary
Mastery target: Level A recognition of each variant's shape and motivation, progressing toward Level B implementation of the compressed trie, binary XOR trie, and ternary search trie.

1. Introduction & Motivation

The standard trie stores one character per node in a hashmap-of-children structure. That design is easy to reason about, but it has real costs: a long chain of single-child nodes wastes both memory and traversal steps, a hashmap per node carries overhead that dwarfs the single byte it indexes, and the character-per-node model does not fit numeric data such as fixed-width integers at all.

Four variants fix different parts of that picture. The compressed trie (radix tree) collapses single-child chains into single edges, cutting node count from one-per-character to roughly one-per-branch-point. The Patricia trie pushes that same idea to the bit level, which is exactly what routers need for longest-prefix-match lookups. The binary trie repurposes the same branching idea for fixed-width binary numbers, unlocking greedy algorithms such as maximum XOR pair. The ternary search trie keeps the memory profile of a binary search tree while retaining prefix-search power, avoiding both the wide array and the hashmap. Finally, the persistent trie shows how any of these structures can keep every past version accessible almost for free.

2. Prerequisites

This lesson builds directly on the Union-Find, Trie, Fenwick & Segment Tree guide, and assumes the standard hash-map-children trie — its insert, search, and starts_with operations, and its $O(L)$ per-operation cost for a key of length $L$ — is already understood. That lesson is not repeated here; every section below assumes you can already build and reason about the plain trie, and instead focuses on what changes structurally in each variant.

3. Compressed Trie / Radix Tree

Core insight: Collapse every chain of single-child nodes into one node holding a substring instead of one character. A radix tree has at most $O(k)$ nodes for $k$ keys, regardless of how long the strings are, because a node only branches where two stored keys actually diverge. That saves both space (no wasted intermediate nodes) and traversal steps (one edge comparison instead of one per character on a chain).
Hand Trace

Inserting "test", "team", "toast"

Start from an empty radix tree and insert three words that share prefixes at different depths. Each insert either extends the tree or splits an existing edge at the point where the new key diverges from what is already stored.

StepInsertExisting edge examinedCommon prefixAction
1test(none — first key)—Create edge "test" from root to a new leaf, marked end-of-word.
2team"test""te" (length 2 of 4)Split "test" at position 2: new internal node under edge "te", with children "st" (old leaf, test) and "am" (new leaf, team).
3toast"te""t" (length 1 of 2)Split "te" at position 1: new internal node under edge "t", with children "e" (leading to the test/team split) and "oast" (new leaf, toast).

The final tree has five nodes total for three words of combined length 13 — a plain trie would need 13 single-character nodes for the same keys (fewer once chains merge, but still far more than five). Every node in the radix tree exists because two or more keys actually disagree there.

Below, each edge is stored as a (label, child) pair keyed by its first character, so a node can still find the right child in $O(1)$ expected time. Inserting compares the new suffix against the stored edge label one character at a time to find the longest common prefix, then either descends past a fully-matched edge or splits a partially-matched one.

class RadixNode:
    def __init__(self):
        self.children = {}  # first_char -> (edge_label, RadixNode)
        self.is_end = False


def _common_prefix_len(a, b):
    i, n = 0, min(len(a), len(b))
    while i < n and a[i] == b[i]:
        i += 1
    return i


class RadixTree:
    def __init__(self):
        self.root = RadixNode()

    def insert(self, word):
        node = self.root
        remaining = word
        while remaining:
            first = remaining[0]
            if first not in node.children:
                leaf = RadixNode()
                leaf.is_end = True
                node.children[first] = (remaining, leaf)
                return
            label, child = node.children[first]
            common = _common_prefix_len(label, remaining)
            if common == len(label):
                remaining = remaining[common:]
                node = child
                if not remaining:
                    node.is_end = True
                    return
                continue
            # Split the edge at position `common`.
            split_node = RadixNode()
            old_suffix = label[common:]
            split_node.children[old_suffix[0]] = (old_suffix, child)
            if common == len(remaining):
                split_node.is_end = True
            else:
                new_suffix = remaining[common:]
                new_leaf = RadixNode()
                new_leaf.is_end = True
                split_node.children[new_suffix[0]] = (new_suffix, new_leaf)
            node.children[first] = (label[:common], split_node)
            return

    def search(self, word):
        node = self.root
        remaining = word
        while remaining:
            first = remaining[0]
            if first not in node.children:
                return False
            label, child = node.children[first]
            if remaining.startswith(label):
                remaining = remaining[len(label):]
                node = child
            else:
                return False
        return node.is_end


tree = RadixTree()
for w in ["test", "team", "toast"]:
    tree.insert(w)

print(tree.search("team"))   # True
print(tree.search("toast"))  # True
print(tree.search("te"))     # False (not a full word)
print(tree.search("tes"))    # False (ends mid-edge)

// Compressed Trie / Radix Tree — insert and search
#include <iostream>
#include <string>
#include <unordered_map>
#include <memory>
using namespace std;

struct RadixNode {
    unordered_map<char, pair<string, unique_ptr<RadixNode>>> children;
    bool isEnd = false;
};

int commonPrefixLen(const string& a, const string& b) {
    int i = 0, n = min(a.size(), b.size());
    while (i < n && a[i] == b[i]) i++;
    return i;
}

class RadixTree {
    unique_ptr<RadixNode> root;
public:
    RadixTree() : root(make_unique<RadixNode>()) {}

    void insert(const string& word) {
        RadixNode* node = root.get();
        string remaining = word;
        while (!remaining.empty()) {
            char first = remaining[0];
            auto it = node->children.find(first);
            if (it == node->children.end()) {
                auto leaf = make_unique<RadixNode>();
                leaf->isEnd = true;
                node->children[first] = {remaining, move(leaf)};
                return;
            }
            string label = it->second.first;
            RadixNode* child = it->second.second.get();
            int common = commonPrefixLen(label, remaining);
            if (common == (int)label.size()) {
                remaining = remaining.substr(common);
                node = child;
                if (remaining.empty()) {
                    node->isEnd = true;
                    return;
                }
                continue;
            }
            // Split the edge at position `common`.
            auto splitNode = make_unique<RadixNode>();
            string oldSuffix = label.substr(common);
            splitNode->children[oldSuffix[0]] = {oldSuffix, move(it->second.second)};
            if (common == (int)remaining.size()) {
                splitNode->isEnd = true;
            } else {
                string newSuffix = remaining.substr(common);
                auto newLeaf = make_unique<RadixNode>();
                newLeaf->isEnd = true;
                splitNode->children[newSuffix[0]] = {newSuffix, move(newLeaf)};
            }
            node->children[first] = {label.substr(0, common), move(splitNode)};
            return;
        }
    }

    bool search(const string& word) const {
        RadixNode* node = root.get();
        string remaining = word;
        while (!remaining.empty()) {
            char first = remaining[0];
            auto it = node->children.find(first);
            if (it == node->children.end()) return false;
            const string& label = it->second.first;
            if (remaining.compare(0, label.size(), label) == 0) {
                remaining = remaining.substr(label.size());
                node = it->second.second.get();
            } else {
                return false;
            }
        }
        return node->isEnd;
    }
};

int main() {
    RadixTree tree;
    for (const string& w : {"test", "team", "toast"}) tree.insert(w);

    cout << boolalpha;
    cout << tree.search("team") << endl;   // true
    cout << tree.search("toast") << endl;  // true
    cout << tree.search("te") << endl;     // false
    cout << tree.search("tes") << endl;    // false
    return 0;
}

// Compressed Trie / Radix Tree — insert and search
import java.util.HashMap;
import java.util.Map;

class RadixNode {
    Map<Character, Edge> children = new HashMap<>();
    boolean isEnd = false;
}

class Edge {
    String label;
    RadixNode target;
    Edge(String label, RadixNode target) { this.label = label; this.target = target; }
}

public class RadixTree {
    private final RadixNode root = new RadixNode();

    private static int commonPrefixLen(String a, String b) {
        int i = 0, n = Math.min(a.length(), b.length());
        while (i < n && a.charAt(i) == b.charAt(i)) i++;
        return i;
    }

    public void insert(String word) {
        RadixNode node = root;
        String remaining = word;
        while (!remaining.isEmpty()) {
            char first = remaining.charAt(0);
            Edge edge = node.children.get(first);
            if (edge == null) {
                RadixNode leaf = new RadixNode();
                leaf.isEnd = true;
                node.children.put(first, new Edge(remaining, leaf));
                return;
            }
            int common = commonPrefixLen(edge.label, remaining);
            if (common == edge.label.length()) {
                remaining = remaining.substring(common);
                node = edge.target;
                if (remaining.isEmpty()) {
                    node.isEnd = true;
                    return;
                }
                continue;
            }
            // Split the edge at position `common`.
            RadixNode splitNode = new RadixNode();
            String oldSuffix = edge.label.substring(common);
            splitNode.children.put(oldSuffix.charAt(0), new Edge(oldSuffix, edge.target));
            if (common == remaining.length()) {
                splitNode.isEnd = true;
            } else {
                String newSuffix = remaining.substring(common);
                RadixNode newLeaf = new RadixNode();
                newLeaf.isEnd = true;
                splitNode.children.put(newSuffix.charAt(0), new Edge(newSuffix, newLeaf));
            }
            node.children.put(first, new Edge(edge.label.substring(0, common), splitNode));
            return;
        }
    }

    public boolean search(String word) {
        RadixNode node = root;
        String remaining = word;
        while (!remaining.isEmpty()) {
            char first = remaining.charAt(0);
            Edge edge = node.children.get(first);
            if (edge == null) return false;
            if (remaining.startsWith(edge.label)) {
                remaining = remaining.substring(edge.label.length());
                node = edge.target;
            } else {
                return false;
            }
        }
        return node.isEnd;
    }

    public static void main(String[] args) {
        RadixTree tree = new RadixTree();
        for (String w : new String[]{"test", "team", "toast"}) tree.insert(w);

        System.out.println(tree.search("team"));   // true
        System.out.println(tree.search("toast"));  // true
        System.out.println(tree.search("te"));     // false
        System.out.println(tree.search("tes"));    // false
    }
}

Patricia Trie

A Patricia trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric) is the same collapsing idea taken to the bit level instead of the byte or character level. Where the radix tree above stores a substring on each edge, a Patricia trie stores a bit-string span, and each node keeps a skip count — the number of bits to skip before the next branching decision — instead of the literal bits themselves. That skip count is enough because the bits being skipped are implied by which branch was taken to reach the node.

This is exactly the structure real routers use for IP routing tables: an IPv4 or IPv6 address is a fixed-width bit string, and a Patricia trie over the address space supports longest-prefix-match lookups — find the most specific CIDR block that contains a given address — in time proportional to the address width, not the number of routes installed. Conceptually:

// Patricia node (conceptual, not implemented here):
// struct PatriciaNode {
//     int skip;              // bits to skip before testing the branch bit
//     PatriciaNode* left;    // branch bit is 0
//     PatriciaNode* right;   // branch bit is 1
// };

This lesson does not build a full Patricia trie — it is a conceptual bridge between the byte-level radix tree above and the bit-level binary trie below. The binary trie in the next section is the simplified, uncompressed version of the same bit-oriented idea, chosen because it is what the classic maximum-XOR interview problem is built on.

4. Binary Trie for XOR (Maximum XOR Pair)

Core insight: Insert each number's binary representation, one bit per level at a fixed width (e.g. 32 bits), into a trie where every node has at most two children — a "bit is 0" child and a "bit is 1" child. To find the value that maximizes the XOR with a given number $x$, walk the trie from the most significant bit, and at each level greedily step toward the opposite bit of $x$ whenever that child exists, because a differing bit contributes $1$ to that position of the XOR result — the largest possible contribution at that level.

This greedy walk solves Maximum XOR of Two Numbers in an Array (LeetCode 421): insert every number into the trie, then for each number query the trie for its best XOR partner, tracking the overall maximum.

class XorTrieNode:
    def __init__(self):
        self.children = [None, None]  # index 0: bit-0 child, index 1: bit-1 child


class XorTrie:
    BITS = 32

    def __init__(self):
        self.root = XorTrieNode()

    def insert(self, num):
        node = self.root
        for i in range(self.BITS - 1, -1, -1):
            bit = (num >> i) & 1
            if node.children[bit] is None:
                node.children[bit] = XorTrieNode()
            node = node.children[bit]

    def max_xor_with(self, num):
        node = self.root
        result = 0
        for i in range(self.BITS - 1, -1, -1):
            bit = (num >> i) & 1
            desired = 1 - bit
            if node.children[desired] is not None:
                result |= (1 << i)
                node = node.children[desired]
            else:
                node = node.children[bit]
        return result


def max_xor_pair(nums):
    trie = XorTrie()
    for num in nums:
        trie.insert(num)
    return max(trie.max_xor_with(num) for num in nums)


sample = [3, 10, 5, 25, 2, 8]
print("Maximum XOR pair:", max_xor_pair(sample))  # 28  (5 ^ 25)

// Binary Trie for XOR — Maximum XOR of Two Numbers in an Array
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct XorTrieNode {
    XorTrieNode* children[2] = {nullptr, nullptr};
};

class XorTrie {
    static const int BITS = 32;
    XorTrieNode* root;
public:
    XorTrie() { root = new XorTrieNode(); }

    void insert(unsigned int num) {
        XorTrieNode* node = root;
        for (int i = BITS - 1; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) node->children[bit] = new XorTrieNode();
            node = node->children[bit];
        }
    }

    unsigned int maxXorWith(unsigned int num) {
        XorTrieNode* node = root;
        unsigned int result = 0;
        for (int i = BITS - 1; i >= 0; --i) {
            int bit = (num >> i) & 1;
            int desired = 1 - bit;
            if (node->children[desired]) {
                result |= (1u << i);
                node = node->children[desired];
            } else {
                node = node->children[bit];
            }
        }
        return result;
    }
};

unsigned int maxXorPair(const vector<unsigned int>& nums) {
    XorTrie trie;
    for (unsigned int num : nums) trie.insert(num);
    unsigned int best = 0;
    for (unsigned int num : nums) best = max(best, trie.maxXorWith(num));
    return best;
}

int main() {
    vector<unsigned int> sample{3, 10, 5, 25, 2, 8};
    cout << "Maximum XOR pair: " << maxXorPair(sample) << endl;  // 28
    return 0;
}

// Binary Trie for XOR — Maximum XOR of Two Numbers in an Array
import java.util.List;

class XorTrieNode {
    XorTrieNode[] children = new XorTrieNode[2];
}

class XorTrie {
    static final int BITS = 32;
    private final XorTrieNode root = new XorTrieNode();

    void insert(int num) {
        XorTrieNode node = root;
        for (int i = BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) node.children[bit] = new XorTrieNode();
            node = node.children[bit];
        }
    }

    int maxXorWith(int num) {
        XorTrieNode node = root;
        int result = 0;
        for (int i = BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int desired = 1 - bit;
            if (node.children[desired] != null) {
                result |= (1 << i);
                node = node.children[desired];
            } else {
                node = node.children[bit];
            }
        }
        return result;
    }
}

public class MaxXorPair {
    static int maxXorPair(List<Integer> nums) {
        XorTrie trie = new XorTrie();
        for (int num : nums) trie.insert(num);
        int best = 0;
        for (int num : nums) best = Math.max(best, trie.maxXorWith(num));
        return best;
    }

    public static void main(String[] args) {
        List<Integer> sample = List.of(3, 10, 5, 25, 2, 8);
        System.out.println("Maximum XOR pair: " + maxXorPair(sample)); // 28
    }
}

Tracing the greedy query for every number in the sample array (5-bit width shown for readability; the code above uses 32 bits):

NumberBinaryBest partnerPartner binaryXOR result
300011251100126
1001010251100119
500101251100128
251100150010128
200010251100127
801000251100117

The overall maximum across every row is $28$, from the pair $(5, 25)$ — exactly what the code prints. Notice that 25 shows up as the best partner for four of the six numbers: its high bits (11) are rare in this array, so it differs early and often, which is precisely what the greedy walk is built to reward.

5. Ternary Search Trie (TST)

Core insight: Give each node exactly three children — less-than, equal, and greater-than the node's stored character — instead of a fixed alphabet-sized array or a hashmap. Comparing against one character per node behaves like a binary search tree (compact, cache-friendly, no wasted slots for absent characters), while following the equal pointer advances to the next character of the key, giving the same prefix-search power as a trie.

Insertion recurses on the current character: go left if it's smaller than the node's character, right if larger, or advance to the next character along the equal link if it matches. Prefix collection is an inorder-style traversal that visits left, then the node itself, then recurses into equal (appending the node's character to the prefix), then right — which yields results in ascending lexicographic order for free.

class TSTNode:
    def __init__(self, char):
        self.char = char
        self.left = None
        self.mid = None
        self.right = None
        self.is_end = False


class TernarySearchTrie:
    def __init__(self):
        self.root = None

    def insert(self, word):
        if word:
            self.root = self._insert(self.root, word, 0)

    def _insert(self, node, word, i):
        ch = word[i]
        if node is None:
            node = TSTNode(ch)
        if ch < node.char:
            node.left = self._insert(node.left, word, i)
        elif ch > node.char:
            node.right = self._insert(node.right, word, i)
        elif i + 1 < len(word):
            node.mid = self._insert(node.mid, word, i + 1)
        else:
            node.is_end = True
        return node

    def search(self, word):
        if not word:
            return False
        node = self._get(self.root, word, 0)
        return node is not None and node.is_end

    def _get(self, node, word, i):
        if node is None:
            return None
        ch = word[i]
        if ch < node.char:
            return self._get(node.left, word, i)
        elif ch > node.char:
            return self._get(node.right, word, i)
        elif i + 1 < len(word):
            return self._get(node.mid, word, i + 1)
        else:
            return node

    def keys_with_prefix(self, prefix):
        results = []
        if not prefix:
            return results
        node = self._get(self.root, prefix, 0)
        if node is None:
            return results
        if node.is_end:
            results.append(prefix)
        self._collect(node.mid, prefix, results)
        return results

    def _collect(self, node, prefix, results):
        if node is None:
            return
        self._collect(node.left, prefix, results)
        if node.is_end:
            results.append(prefix + node.char)
        self._collect(node.mid, prefix + node.char, results)
        self._collect(node.right, prefix, results)


t = TernarySearchTrie()
for w in ["cat", "car", "cart", "dog", "do"]:
    t.insert(w)

print(t.search("car"))              # True
print(t.search("ca"))               # False (not a full word)
print(t.keys_with_prefix("ca"))     # ['car', 'cart', 'cat']
print(t.keys_with_prefix("do"))     # ['do', 'dog']

// Ternary Search Trie — insert, search, prefix collection
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct TSTNode {
    char ch;
    TSTNode* left = nullptr;
    TSTNode* mid = nullptr;
    TSTNode* right = nullptr;
    bool isEnd = false;
    TSTNode(char c) : ch(c) {}
};

class TernarySearchTrie {
    TSTNode* root = nullptr;

    TSTNode* insertHelper(TSTNode* node, const string& word, size_t i) {
        char ch = word[i];
        if (node == nullptr) node = new TSTNode(ch);
        if (ch < node->ch) {
            node->left = insertHelper(node->left, word, i);
        } else if (ch > node->ch) {
            node->right = insertHelper(node->right, word, i);
        } else if (i + 1 < word.size()) {
            node->mid = insertHelper(node->mid, word, i + 1);
        } else {
            node->isEnd = true;
        }
        return node;
    }

    TSTNode* get(TSTNode* node, const string& word, size_t i) const {
        if (node == nullptr) return nullptr;
        char ch = word[i];
        if (ch < node->ch) return get(node->left, word, i);
        if (ch > node->ch) return get(node->right, word, i);
        if (i + 1 < word.size()) return get(node->mid, word, i + 1);
        return node;
    }

    void collect(TSTNode* node, const string& prefix, vector<string>& results) const {
        if (node == nullptr) return;
        collect(node->left, prefix, results);
        if (node->isEnd) results.push_back(prefix + node->ch);
        collect(node->mid, prefix + node->ch, results);
        collect(node->right, prefix, results);
    }

public:
    void insert(const string& word) {
        if (!word.empty()) root = insertHelper(root, word, 0);
    }

    bool search(const string& word) const {
        if (word.empty()) return false;
        TSTNode* node = get(root, word, 0);
        return node != nullptr && node->isEnd;
    }

    vector<string> keysWithPrefix(const string& prefix) const {
        vector<string> results;
        if (prefix.empty()) return results;
        TSTNode* node = get(root, prefix, 0);
        if (node == nullptr) return results;
        if (node->isEnd) results.push_back(prefix);
        collect(node->mid, prefix, results);
        return results;
    }
};

int main() {
    TernarySearchTrie t;
    for (const string& w : {"cat", "car", "cart", "dog", "do"}) t.insert(w);

    cout << boolalpha;
    cout << t.search("car") << endl;   // true
    cout << t.search("ca") << endl;    // false

    for (const string& key : t.keysWithPrefix("ca")) cout << key << " ";
    cout << endl;  // car cart cat

    for (const string& key : t.keysWithPrefix("do")) cout << key << " ";
    cout << endl;  // do dog
    return 0;
}

// Ternary Search Trie — insert, search, prefix collection
import java.util.ArrayList;
import java.util.List;

class TSTNode {
    char ch;
    TSTNode left, mid, right;
    boolean isEnd = false;
    TSTNode(char ch) { this.ch = ch; }
}

public class TernarySearchTrie {
    private TSTNode root;

    public void insert(String word) {
        if (!word.isEmpty()) root = insert(root, word, 0);
    }

    private TSTNode insert(TSTNode node, String word, int i) {
        char ch = word.charAt(i);
        if (node == null) node = new TSTNode(ch);
        if (ch < node.ch) {
            node.left = insert(node.left, word, i);
        } else if (ch > node.ch) {
            node.right = insert(node.right, word, i);
        } else if (i + 1 < word.length()) {
            node.mid = insert(node.mid, word, i + 1);
        } else {
            node.isEnd = true;
        }
        return node;
    }

    public boolean search(String word) {
        if (word.isEmpty()) return false;
        TSTNode node = get(root, word, 0);
        return node != null && node.isEnd;
    }

    private TSTNode get(TSTNode node, String word, int i) {
        if (node == null) return null;
        char ch = word.charAt(i);
        if (ch < node.ch) return get(node.left, word, i);
        if (ch > node.ch) return get(node.right, word, i);
        if (i + 1 < word.length()) return get(node.mid, word, i + 1);
        return node;
    }

    public List<String> keysWithPrefix(String prefix) {
        List<String> results = new ArrayList<>();
        if (prefix.isEmpty()) return results;
        TSTNode node = get(root, prefix, 0);
        if (node == null) return results;
        if (node.isEnd) results.add(prefix);
        collect(node.mid, prefix, results);
        return results;
    }

    private void collect(TSTNode node, String prefix, List<String> results) {
        if (node == null) return;
        collect(node.left, prefix, results);
        if (node.isEnd) results.add(prefix + node.ch);
        collect(node.mid, prefix + node.ch, results);
        collect(node.right, prefix, results);
    }

    public static void main(String[] args) {
        TernarySearchTrie t = new TernarySearchTrie();
        for (String w : new String[]{"cat", "car", "cart", "dog", "do"}) t.insert(w);

        System.out.println(t.search("car"));         // true
        System.out.println(t.search("ca"));          // false
        System.out.println(t.keysWithPrefix("ca"));  // [car, cart, cat]
        System.out.println(t.keysWithPrefix("do"));  // [do, dog]
    }
}

6. Persistent Trie

Every trie variant above mutates in place: inserting a word changes the tree, and the previous version is gone. A persistent trie keeps every version reachable instead, using a technique called path copying. When a word is inserted, only the nodes that lie on the path from the root to the modified leaf are cloned; every other subtree is left untouched and simply shared, by pointer, between the old version and the new one.

Because a trie's path length for one key is bounded by the key's length (or bit width, for a binary trie), path copying touches only $O(L)$ nodes per update no matter how large the overall structure is — the new version costs a small, bounded amount of extra memory rather than a full copy. The old root pointer still describes the tree exactly as it was before the insert, so both versions can be queried independently and forever.

Persistence as a general technique — applying path copying to balanced trees, arrays, and other structures, along with fat nodes and other space-saving refinements — is broad enough to deserve its own treatment. This lesson only introduces the idea as it applies to a trie; a dedicated Persistent Trees lesson in a later part of the curriculum covers the general technique in depth.

7. Complexity Comparison Table

StructureSpaceInsertSearch
Standard trie (hashmap children)$O(N \cdot L)$ nodes, high per-node overhead$O(L)$$O(L)$
Compressed trie / radix tree$O(n)$ nodes ($\le 2n-1$)$O(L)$ amortized$O(L)$
Binary trie (fixed $B$-bit keys)$O(n \cdot B)$ nodes$O(B)$$O(B)$
Ternary search trie$O(n \cdot L)$ nodes, 3 pointers each (low overhead)$O(L)$ average$O(L)$ average

Here $n$ is the number of stored keys, $L$ is average key length, $N \cdot L$ is total character count across all keys, and $B$ is the fixed bit width (32 for a typical integer). The radix tree wins on node count; the ternary search trie wins on per-node overhead; the binary trie is the only one shaped for numeric greedy algorithms like maximum XOR.

8. Applications & Alternatives

Where each variant is the right default

  • Patricia tries: IP routing tables and longest-prefix-match lookups in routers and firewalls.
  • Radix trees: filesystem path tables, URL routers, and any large set of strings with long shared prefixes.
  • Binary tries: maximum XOR pair/subarray problems, and IP-mask style bit manipulation.
  • Ternary search tries: autocomplete and spell-check dictionaries where memory per node matters more than raw speed.
  • Persistent tries: version-controlled dictionaries, undo/redo over prefix-searchable data, and functional-language string sets.

Alternatives worth weighing before reaching for any trie variant: a plain hash set gives $O(L)$ exact-match lookups with excellent cache behavior when prefix queries are not needed at all. A Bloom filter trades exactness for a fixed, tiny memory footprint when false positives are tolerable. Suffix trees and suffix arrays solve a different problem — substring search anywhere inside a text — rather than prefix search over a set of whole keys, and are worth reaching for only when that is the actual requirement.

9. Exercises

Easy

  1. By hand, insert "go", "gone", "good" into an empty radix tree in that order, and draw the resulting node/edge structure at each step.
  2. Given a working insert for a radix tree, implement search and verify it against the "test"/"team"/"toast" example above.

Medium

  1. Solve Maximum XOR of Two Numbers in an Array (LeetCode 421) using the binary trie above, then extend it to a variant: given a target value $v$ and a range, find the maximum XOR achievable with a value from the array that also falls within that range.
  2. Extend the binary trie query to return the pair of numbers achieving the maximum XOR, not just the XOR value itself.

Hard

  1. Implement autocomplete (prefix listing, ordered lexicographically) on top of a ternary search trie, using keys_with_prefix as the foundation, and add a result-count limit for large dictionaries.
  2. Add a delete operation to the radix tree that merges a node back into its parent's edge when a deletion leaves it with a single child and no stored word.
Mastery challenge: A network device must answer "which of these million routes best matches this incoming packet's destination address?" in the time budget of a single packet. Choose between a radix tree, a Patricia trie, and a plain hash set; justify the choice using the space/insert/search table above, and describe what changes if routes are added and withdrawn constantly while lookups must never block.

Review rhythm: tomorrow, redraw the radix-tree split from the hand trace without looking; next week, re-implement the binary XOR trie and the ternary search trie from memory in one sitting; several weeks later, identify which of these four variants best fits a new prefix- or bit-oriented problem before writing any code.

10. Summary Cheat Sheet

  • A compressed trie (radix tree) collapses single-child chains into substring-labeled edges, giving $O(k)$ nodes for $k$ keys.
  • A Patricia trie is the bit-level version of a radix tree, storing a skip count per node instead of a substring — the structure behind router longest-prefix-match.
  • A binary trie stores fixed-width bit representations; greedily preferring the opposite bit at each level solves maximum-XOR problems.
  • A ternary search trie uses three children per node (less/equal/greater) instead of an array or hashmap, combining BST-like space efficiency with trie-like prefix search.
  • A persistent trie uses path copying to keep every past version queryable, cloning only the $O(L)$ nodes on the modified path.
  • Choose by workload: radix/Patricia for space and longest-prefix-match, binary trie for numeric XOR queries, TST for memory-constrained prefix search, and a plain hash set when prefix queries are not needed at all.

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Browse the complete 18-level algorithm curriculum and practical project sequence.

Open the DSA Hub
Union-Find, Trie, Fenwick & Segment Tree

Build the standard hash-map-children trie this lesson assumes, alongside Union-Find and range-query structures.

Read the Advanced Structures Guide
Bit Manipulation

Deepen the bitwise operations that power the binary trie and maximum-XOR techniques covered here.

Read the Bit Manipulation Guide