Bitwise Trie Concept

Store each number as a 32-bit binary string in the trie. Each node has at most 2 children: 0 and 1.

For XOR, you want corresponding bits to differ. When finding the maximum XOR partner for a number:

• At each bit, try to go the opposite direction
• If opposite doesn't exist, go the same direction
• Build the XOR result bit by bit

function findMaxXOR(num, root):
    node = root
    xor = 0
    for i from 31 down to 0:
        bit = (num >> i) & 1
        oppositeBit = 1 - bit
        if node.children[oppositeBit]:
            xor |= (1 << i)
            node = node.children[oppositeBit]
        else:
            node = node.children[bit]
    return xor

Process from most significant bit to least significant. Higher bits contribute more to the result.