Advanced Trie Applications — XOR, Palindrome Pairs, Stream Search

class BinaryTrie:
    def __init__(self):
        self.root = {}

    def insert(self, num):
        node = self.root
        for bit in range(31, -1, -1):
            b = (num >> bit) & 1
            if b not in node: node[b] = {}
            node = node[b]

    def max_xor(self, num):
        node = self.root
        xor = 0
        for bit in range(31, -1, -1):
            b = (num >> bit) & 1
            want = 1-b
            if want in node:
                xor |= (1 << bit)
                node = node[want]
            else:
                node = node[b]
        return xor

def findMaximumXOR(nums):
    trie = BinaryTrie()
    for n in nums: trie.insert(n)
    return max(trie.max_xor(n) for n in nums)

def palindromePairs(words):
    word_map = {w: i for i, w in enumerate(words)}
    res = []

    def is_pal(s, l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True

    for i, w in enumerate(words):
        n = len(w)
        for j in range(n+1):
            if is_pal(w, j, n-1):
                rev = w[:j][::-1]
                if rev in word_map and word_map[rev] != i:
                    res.append([i, word_map[rev]])
            if j > 0 and is_pal(w, 0, j-1):
                rev = w[j:][::-1]
                if rev in word_map and word_map[rev] != i:
                    res.append([word_map[rev], i])
    return res

function findMaximumXOR(nums){
    const trie={};
    for(const n of nums){let node=trie;for(let b=31;b>=0;b--){const bit=(n>>b)&1;if(!(bit in node))node[bit]={};node=node[bit];}}
    let max=0;
    for(const n of nums){let node=trie,xor=0;for(let b=31;b>=0;b--){const bit=(n>>b)&1,want=1-bit;if(want in node){xor|=1<<b;node=node[want];}else node=node[bit];}max=Math.max(max,xor);}
    return max;
}

/* Binary Trie: int[2] children array, insert nums, greedy XOR query */

/* C++: array-based trie, children[2] per node, same greedy XOR approach */

/* C: static trie array, same bit-by-bit XOR maximization */