Trie Advanced Applications — XOR Tries, Word Filters, and Compressed Tries

Problem and Topic Statement#

The basic trie supports insert and prefix-search in O(L) time per operation where L is key length. The advanced trie family extends this skeleton in five major directions, each unlocking a class of FAANG-hard problems:

1. XOR tries (binary tries) — store integers as bit sequences and answer maximum-XOR-pair queries in O(32). Powers LC 421 (Maximum XOR of Two Numbers in an Array) and LC 1707 (Maximum XOR With an Element from Array).
2. Prefix-and-suffix tries — answer combined prefix and suffix queries by indexing pairs of suffixes and prefixes. Powers LC 745 (Prefix and Suffix Search).
3. Ternary search tries — branch on character comparison rather than character value, saving memory on sparse alphabets.
4. Compressed tries (PATRICIA) — collapse single-child chains, used in IP routing and the Linux kernel.
5. Persistent tries — share structure across versions, enabling O(log n) historical queries used in functional language internals and version-controlled dictionaries.

This blog covers when to reach for each variant and the FAANG problems where they shine.

Why This Topic Matters#

Tries are deceptively shallow at first glance — most candidates know how to insert and prefix-search a trie before their first interview. But the advanced applications differentiate strong candidates. Knowing that a maximum-XOR query becomes a binary trie walk is the kind of insight Google and Meta interviewers grade for in their hard onsite slots.

In production, advanced tries appear in places you might not expect. The Linux kernel uses radix trees (compressed tries) to map page indices to memory pages. IP routing tables use PATRICIA tries to match longest-prefix CIDR ranges in O(32) time per packet. Search engines use ternary search tries for memory-efficient autocomplete on Unicode dictionaries. The Lucene postings list uses compressed tries to map terms to document IDs.

The transferable skill from this family is structural pattern recognition. When you see "maximum XOR" you should think binary trie. When you see "find words matching prefix and suffix" you should think suffix-augmented trie. Once you internalise these mappings, the FAANG hard pile shrinks dramatically.

The Core Insight#

A trie is a tree where each path from root to a node represents a prefix of some inserted key. The advanced variants modify three things: the alphabet (binary, ternary, or compressed labels), the payload (counts, lists, or version pointers), and the search semantics (max-XOR walk, longest-prefix match, range queries).

XOR trie. Insert each integer as a 32-bit (or 64-bit) sequence into a binary trie. To find the integer x in the trie that maximises x XOR query, walk the trie bit by bit; at each level prefer the bit that differs from the current bit of query, falling back to the other bit if no such child exists. Each query is O(32). The set of all pairwise maximum XORs over an array is then n queries in O(32n).

Prefix-and-suffix trie. For each word w, insert every (suffix, prefix) pair s + '#' + w into a trie. A query (P, S) becomes "find a path matching S + '#' + P". The trie returns the maximum-index word among the matching candidates. Total preprocessing O(n*L^2), per-query O(P+S+1).

Ternary search trie. Each node has three children: less-than, equal-to, greater-than the node's character. Equality children advance to the next character of the key. This saves memory on sparse alphabets compared to a 26-array per node, at the cost of a logarithmic factor inside the equal walk. Useful when the alphabet is large (full Unicode) or memory is tight.

Compressed trie / radix tree / PATRICIA. Single-child chains collapse into a single edge labelled with the concatenated characters. Insertions and queries split edges as needed. Memory is O(n) total characters across all edges, optimal. IP routing tables use this with bit-level edges.

Persistent trie. Each insertion creates a new root that shares unmodified subtrees with the previous version. Memory grows by O(L) per insertion. Historical queries and time-travel debugging become free.

Visual Dry Run / Worked Example#

XOR trie example. Array [3, 10, 5, 25, 2, 8], find the maximum pairwise XOR.

Convert each to 5-bit binary (since max is 25 which is 11001):

3  = 00011
10 = 01010
5  = 00101
25 = 11001
2  = 00010
8  = 01000

Insert all into a binary trie. Then for each number x, walk the trie preferring the opposite bit of x at each level. For x = 5 (00101), the greedy walk prefers 1xxxx then within that prefers 01xxx and so on, leading to 25 (11001). 5 XOR 25 = 11100 = 28.

Try x = 25; greedy prefers 0 at the top bit, leading to 5. 25 XOR 5 = 28.

Maximum pairwise XOR is 28.

Prefix-and-suffix trie example. Words = ["apple", "ample"]. Insert all (suffix, prefix) pairs:

"apple#apple", "pple#apple", "ple#apple", "le#apple", "e#apple", "#apple"
"ample#ample", "mple#ample", "ple#ample", "le#ample", "e#ample", "#ample"

Query (prefix="a", suffix="le"): build search key "le#a". Walk the trie. Both "le#apple" and "le#ample" match the path "le#a". Return the maximum-index word, say apple if it was inserted last.

Solution (Optimal)#

XOR Trie — Maximum XOR of Two Numbers (LC 421) — Python#

def findMaximumXOR(nums):
    root = {}
    for num in nums:
        node = root
        for i in range(31, -1, -1):
            b = (num >> i) & 1
            node = node.setdefault(b, {})
 
    best = 0
    for num in nums:
        node = root
        cur = 0
        for i in range(31, -1, -1):
            b = (num >> i) & 1
            want = 1 - b
            if want in node:
                cur |= (1 << i)
                node = node[want]
            else:
                node = node[b]
        best = max(best, cur)
    return best

XOR Trie — JavaScript#

function findMaximumXOR(nums) {
  const root = {};
  for (const num of nums) {
    let node = root;
    for (let i = 31; i >= 0; i--) {
      const b = (num >> i) & 1;
      if (!node[b]) node[b] = {};
      node = node[b];
    }
  }
  let best = 0;
  for (const num of nums) {
    let node = root;
    let cur = 0;
    for (let i = 31; i >= 0; i--) {
      const b = (num >> i) & 1;
      const want = 1 - b;
      if (node[want]) {
        cur |= (1 << i);
        node = node[want];
      } else {
        node = node[b];
      }
    }
    if (cur > best) best = cur;
  }
  return best;
}

Complexity: O(32n) build, O(32n) query. Memory: O(32n) trie nodes.

Prefix-and-Suffix Trie — Python sketch#

class WordFilter:
    def __init__(self, words):
        self.trie = {}
        for idx, w in enumerate(words):
            for i in range(len(w) + 1):
                key = w[i:] + '#' + w
                node = self.trie
                for ch in key:
                    node = node.setdefault(ch, {})
                    node['$'] = idx
 
    def f(self, prefix, suffix):
        key = suffix + '#' + prefix
        node = self.trie
        for ch in key:
            if ch not in node:
                return -1
            node = node[ch]
        return node.get('$', -1)

Build O(N*L^2). Query O(P+S+1).

Common Mistakes#

• Storing integers as strings in an XOR trie rather than walking bits directly. Slower and uses more memory.
• Forgetting fallback in the XOR walk. If the preferred bit child does not exist, you still need to descend into the only available child to keep advancing.
• Mishandling negative numbers in XOR tries — agree on signed-vs-unsigned representation upfront, or shift to all non-negative.
• Inserting only suffixes (not all suffix-prefix pairs) for prefix-and-suffix tries — you get incorrect prefix matching.
• Using a 26-array per node when the alphabet is huge. Switch to a hash map per node or a ternary search trie.
• Forgetting that compressed tries split edges on insert. Edge splitting is the trickiest part of PATRICIA; many implementations get it wrong.

Interview Tips#

Identify the trie variant from problem keywords. "Maximum XOR" implies binary trie. "Prefix and suffix" implies the suffix-augmented trie trick. "IP longest prefix" implies PATRICIA. State the mapping out loud — it earns immediate credit for pattern recognition.

For XOR tries, walk through one bit-level greedy step on the whiteboard. The fallback case (preferred bit unavailable) is what most candidates miss; mention it explicitly.

For prefix-and-suffix tries, articulate the cost trade-off: O(NL^2) build vs O(NL) for naive search per query. The trie wins when you have many queries.

If memory is a concern, mention ternary search tries or hash-map-based tries. Knowing these alternatives signals depth beyond the standard 26-array implementation.

Follow-up Questions#

1. Maximum XOR with constraint that element index is at most k (LC 1707). Process queries offline sorted by limit, inserting numbers up to limit before each query.
2. Range XOR queries. Augment the binary trie with subtree counts; do a binary search per query.
3. Compressed trie for IP routing. Each edge is a bit string of variable length. Longest-prefix match is a single trie walk.
4. Persistent trie for version control of dictionaries. Each insert creates a new root and shares unmodified subtrees; memory grows by O(L) per version.
5. Trie compression for memory-bound applications. Use a DAWG (directed acyclic word graph) which deduplicates not just prefixes but also suffixes.

Key Takeaways#

• The basic trie skeleton — children dict, terminal marker, O(L) operations — is the foundation; advanced applications modify alphabet, payload, or search semantics.
• XOR tries reduce maximum-XOR-pair queries from O(n^2) to O(32n) by walking 32 bits per query.
• Prefix-and-suffix tries index every (suffix, prefix) pair; cost O(N*L^2) preprocessing buys O(P+S) per query.
• Ternary search tries save memory on sparse alphabets at a small log-factor cost; useful for full-Unicode dictionaries.
• Compressed tries (PATRICIA) collapse single-child chains; used in IP routing and the Linux kernel page cache.
• Persistent tries enable historical queries with O(L) memory per version; foundational to functional dictionaries and time-travel debugging.
• Pattern recognition is the FAANG signal: see the trie variant in the problem statement and name it explicitly.