Tries & Prefix Search Engines

The Maximum XOR problem is the ultimate showcase of how bit manipulation and trees blend together. Once you see the greedy nature of binary numbers, the Binary Trie solution becomes second nature.

1. The Greedy Bit Principle

In binary numbers, the Most Significant Bit (MSB) has more numerical value than all lower bits combined! For example, bit 30 ($2^{30} pprox 1.07 imes 10^9$) is strictly greater than the sum of all bits from 0 to 29 combined ($2^{30} – 1$).

Therefore, to maximize an XOR sum, you must be greedy from left to right (MSB down to LSB):

• If the current bit of number num is 1, you desperately want to pair it with a number whose corresponding bit is 0 (because 1 ^ 0 = 1).
• If the current bit of num is 0, you want to pair it with a number whose corresponding bit is 1 (because 0 ^ 1 = 1).

2. Why a Binary Trie?

A Binary Trie is just a tree where every node has at most two children: 0 (left) and 1 (right).

1. Insert: You insert each number into the Trie as a 31-bit or 32-bit string of binary digits, from bit 31 down to bit 0.
2. Query: For each number x, you walk down the Trie. At each bit b, you ask: ‘Does the opposite branch (1 - b) exist?’
   • If YES: Take that branch! That bit in your XOR result becomes 1.
   • If NO: You’re forced to take the same branch (b), so that bit in your XOR result becomes 0.

Because you made the best possible choice at every single bit position starting from the highest power of 2, the final accumulated number is mathematically guaranteed to be the global maximum XOR!

Clean Python 3.12 Implementation

class TrieNode:
    __slots__ = ('children',)
    def __init__(self):
        self.children: list[TrieNode | None] = [None, None]

class Solution:
    def find_maximum_xor(self, nums: list[int]) -> int:
        root = TrieNode()

        # Step 1: Insert all numbers into the 31-bit binary trie
        for num in nums:
            curr = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if not curr.children[bit]:
                    curr.children[bit] = TrieNode()
                curr = curr.children[bit]

        # Step 2: Query each number against the trie
        max_xor = 0
        for num in nums:
            curr = root
            current_xor = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                opposite_bit = 1 - bit
                
                # Greedily check if the complementary bit exists
                if curr.children[opposite_bit]:
                    current_xor |= (1 << i)
                    curr = curr.children[opposite_bit]
                else:
                    curr = curr.children[bit]
                    
            max_xor = max(max_xor, current_xor)

        return max_xor

Complexity Breakdown

• Time Complexity: O(31 * N) = O(N). Inserting N numbers takes 31 * N operations. Querying N numbers takes 31 * N operations. Total time is strictly linear in the number of elements.
• Space Complexity: O(31 * N) worst-case node allocations. In practice, prefix branches overlap heavily, keeping memory around a few megabytes.