Everything you've learned about tries so far assumed a 26-letter alphabet. Nodes have up to 26 children. Paths spell out English words. But the trie doesn't care about English. It cares about sequences of symbols from a fixed alphabet. Change the alphabet, and the trie still works — it just changes shape.

What if the alphabet has only two symbols: 0 and 1?

Now you're storing numbers as their binary representations. The integer 5 becomes the bit string 101. The integer 3 becomes 011. Each node has at most two children — a 0-child and a 1-child — so the trie becomes a binary tree where depth corresponds to bit position.

This is already interesting, but here's where it gets powerful. In the letter-trie world, the question was “find words with this prefix.” In the bit-trie world, the question becomes: "find the number that disagrees with mine as much as possible."

Why would you want maximum disagreement? Because disagreement in binary has a name: XOR. The XOR of two bits is 1 when they differ and 0 when they match. Maximizing XOR means maximizing the number of differing bit positions — and a trie lets you do that greedily, one bit at a time, from the most significant bit down.

Try it yourself — type any number below and see how it becomes a binary path. Each bit is a left/right choice in the trie.

Here's the problem: given an array of integers, find the pair with the maximum XOR. The brute-force approach checks every pair — O(N^2). Can the trie do better?

The strategy is greedy, and it exploits a property of binary arithmetic that feels almost too convenient. Insert all numbers into a binary trie, most significant bit first. Each number becomes a path of 0s and 1s from root to leaf, just like words became paths of letters in the earlier trie. The difference is that this alphabet has only two symbols, so the trie is a binary tree.

Now, for each number in the array, walk the trie trying to take the opposite path at every level. If your current bit is 0, you want to go to the 1-child — that maximizes disagreement at that bit position. If the opposite child doesn't exist, you're forced to take the matching one, contributing 0 to the XOR at that bit. Each level is an independent decision: take the opposite if you can, settle for the same if you must.

Why does greedy work here? Because bit positions have strict priority. Disagreeing at bit 31 (the MSB) contributes 2^31 to the result. Disagreeing at every bit from 0 through 30 combined contributes at most 2^31 - 1. So a single high-bit disagreement outweighs all lower bits combined. There's no tradeoff to agonize over — you always grab the highest available disagreement first.

Build the trie below, then navigate it for maximum XOR. Watch how the greedy choice at each level compounds: the bits you lock in early dominate the final result, and the later bits are just tiebreakers.

Let's crystallize why the greedy approach you just used actually produces the optimal answer, not just a good one.

In XOR, each bit position is independent. Bit 31 contributes 2^31 to the result. Bit 30 contributes 2^30. All of bits 0 through 30 combined contribute at most 2^31 - 1 — still less than bit 31 alone. This means disagreeing at a higher bit always beats agreeing at every lower bit. There's no trade-off to consider, no “sacrifice this bit to gain those three.” Higher bits have absolute priority.

When a problem has this kind of strict priority ordering — where the best choice at each level is always locally correct and globally optimal — greedy works. It's the same principle behind Huffman coding (always merge the two smallest frequencies) and MSB-first radix sort (most significant digit determines the coarsest bucket). The structure of the problem guarantees that local optimization cascades into global optimization.

The complexity tells the real story. Brute force checks every pair: O(N^2). With N = 100,000 that's 10 billion comparisons. The XOR trie inserts all N numbers in O(N * B) time, then queries each in O(B), for a total of O(N * B). With 32-bit integers, that's about 3.2 million operations — over 3,000x faster.

And notice: this is still just a trie. The same insert logic (walk or create), the same search logic (walk and decide at each node). The only things that changed were the alphabet (2 symbols instead of 26) and the decision rule at each level (prefer the opposite child instead of the matching one). The structure carries over. The thinking transfers.

Toggle between insert and maxXOR below. The insert is identical to letter-trie insert. The query adds one twist: prefer the opposite bit.

function insert(num: number) {

  let node = this.root

  for (let i = 31; i >= 0; i--) {

    const bit = (num >> i) & 1

    if (!node.children[bit]) {

      node.children[bit] = new TrieNode()

    }

    node = node.children[bit]

  }

}