Advanced Trie

Max XOR (Bit Trie)

Store numbers as 32-bit binary strings in a trie (each node has children 0 and 1). To find the max XOR for a number, greedily choose the opposite bit at each level (1 if you have 0, 0 if you have 1). This maximizes each bit position.

O(n * 32)

say this out loud

I store numbers as bit paths and greedily take the opposite bit at each level, because a win at a higher bit outweighs everything below it.

How It Works

A binary trie stores each number as its 32-bit path from the most significant bit down, every node having at most two children (0 and 1). To find which stored number maximizes XOR with a query value, walk from the root and at each bit greedily take the child opposite to the query's bit. An opposite bit contributes a 1 to that XOR position. If the opposite child is missing, settle for the same-bit child and continue.

The greedy is safe because bit positions are independent and higher bits dominate: securing a 1 at bit k outweighs every possible gain from bits below it combined. Each insertion and each query costs O(32) = O(1) per number, so Maximum XOR over n numbers runs in O(32n), replacing the O(n^2) all-pairs comparison. The same structure answers online queries with constraints, as in Maximum XOR With an Element From Array.

Step-by-Step Visualization

Find the pair in [3, 10, 5, 25, 2] with the largest XOR. Checking every pair is O(n squared)

best0

1/9

Code

Java

static int findMaxXOR(int[] nums) {
  Map<Integer, Map<Integer, Object>> trie = new HashMap<>();

  int max = 0;
  for (int num : nums) {
    // Insert num into bit trie
    Map<Integer, Object> node = trie.computeIfAbsent(0, k -> new HashMap<>());
    for (int i = 31; i >= 0; i--) {
      int bit = (num >> i) & 1;
      node = (Map<Integer, Object>) ((Map)node).computeIfAbsent(bit, k -> new HashMap<>());
    }
    // Query for max XOR
    node = (Map<Integer, Object>) trie.get(0);
    int xor = 0;
    for (int i = 31; i >= 0; i--) {
      int bit = (num >> i) & 1;
      int want = 1 - bit;
      if (((Map)node).containsKey(want)) { xor |= (1 << i); node = (Map)((Map)node).get(want); }
      else node = (Map)((Map)node).get(bit);
    }
    max = Math.max(max, xor);
  }
  return max;
}

Tips & Gotchas

1Store numbers as 32-bit binary in a trie (each node has children 0 and 1)

2To maximize XOR with a number, greedily pick the opposite bit at each level

3Process from most significant bit to least significant

Practice Problems

1Maximum XOR of Two Numbers in an Array
2Maximum XOR With an Element From Array
3Count Pairs With XOR in a Range

About the Advanced Trie Pattern

Extend the basic trie to handle wildcards, combine with DFS for grid search, or store binary representations of numbers for XOR optimization.

Key insight

Use a trie when you need prefix-based operations that hash maps can't do efficiently, like 'find all words starting with X' or 'find word matching pattern with wildcards'.

Common Trie Interview Problems

Implement Trie
Word Search II
Design Add and Search Words
Replace Words
Maximum XOR of Two Numbers

Frequently Asked Questions

Why is greedily choosing the opposite bit at each level correct?

The XOR contribution of bit k is 2^k, which strictly exceeds the sum of all lower bit contributions (2^k > 2^(k-1) + ... + 1). Locking in a mismatch at a high bit therefore beats any combination of wins at lower bits, so the top-down greedy can never be improved by backtracking.

How does the bit trie compare to the hash-set prefix method for Maximum XOR?

Both run in O(32n). The hash method iterates bit positions, guessing each answer bit and verifying with set lookups; the trie makes one pass per query with simpler reasoning and extends naturally to online insertion, deletion (with node counts), and value-limited queries, at the cost of more memory for nodes.

How do I support deletions from a binary trie?

Store a pass-through counter on every node, incremented on insert and decremented on delete. During queries, treat a child with count zero as absent. This keeps all operations O(32) without physically freeing nodes.