Bitwise trie (maximum XOR)

A bitwise trie (also called a binary trie) is a trie whose alphabet is just 0 and 1. Each number is inserted as a fixed-length path of its bits, starting from the most significant bit. For 32-bit integers every path has the same depth, so each insert and query takes a constant 32 (or 31) steps.

Its main interview use is maximising XOR. XOR gives 1 where two bits differ, and a 1 in a higher bit is worth more than all lower bits combined (2^4 = 16 is more than 8 + 4 + 2 + 1 = 15). So to get the biggest XOR with x, you want the opposite of x's bit at the highest position possible, then the next, and so on. The trie lets you make that greedy choice one level at a time.

1. 1Pick a bit width B large enough for the inputs, such as 31 for non-negative 32-bit integers.
2. 2Insert a number: for i from B-1 down to 0, take bit b = (x >> i) & 1 and follow or create child b.
3. 3Query the best partner for x: at each level, compute the bit you want, the opposite of x's bit. If that child exists, go there and set bit i of the result to 1. Otherwise follow the same bit, and that result bit stays 0.
4. 4Because a higher bit outweighs all lower ones together, choosing the opposite bit whenever possible, from the top down, always gives the maximum XOR.
5. 5For the whole array, insert each number and query it against the trie, keeping the best answer. Inserting before querying guarantees the trie is never empty (a number XOR itself is just 0).

def find_maximum_xor(nums, bits=31):
    root = {}

    def insert(x):
        node = root
        for i in range(bits - 1, -1, -1):      # most significant bit first
            b = (x >> i) & 1
            node = node.setdefault(b, {})

    def best_xor(x):
        node, result = root, 0
        for i in range(bits - 1, -1, -1):
            b = (x >> i) & 1
            want = 1 - b                       # opposite bit makes this XOR bit 1
            if want in node:
                result |= 1 << i
                node = node[want]
            else:
                node = node[b]                 # always exists: x itself is stored
        return result

    best = 0
    for x in nums:
        insert(x)                              # insert first so the trie is never empty
        best = max(best, best_xor(x))
    return best

Each number becomes a 31-level path of bits, highest first. best_xor prefers the opposite bit at every level, setting that result bit to 1 when possible. Inserting x before querying keeps the trie non-empty and guarantees node[b] exists. Time O(n x 31), space O(n x 31) nodes in the worst case.

Cost: Insert and query O(B) each, where B is the bit width (31 or 32). Whole array: O(n x B) time, O(n x B) nodes in the worst case.