Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 15 of 32

Binary Trie for XOR Problems

May 2026 · 28 min read

A binary trie stores numbers by their bits from most significant to least significant. It is the standard data structure for maximum XOR queries because XOR wants opposite bits: to maximize x ^ y, try to pair each bit of x with the opposite bit of y.

Trie Structure

Each node has up to two children, one for bit 0 and one for bit 1. Store a count if you need deletion or multiset behavior.

struct BinaryTrie {
    struct Node {
        int child[2] = {-1, -1};
        int cnt = 0;
    };

    vector<Node> tr;
    static const int LOG = 31;

    BinaryTrie() { tr.push_back(Node()); }
};

Insertion

void insert(int x) {
    int u = 0;
    tr[u].cnt++;
    for (int b = LOG; b >= 0; --b) {
        int bit = (x >> b) & 1;
        if (tr[u].child[bit] == -1) {
            tr[u].child[bit] = tr.size();
            tr.push_back(Node());
        }
        u = tr[u].child[bit];
        tr[u].cnt++;
    }
}

Maximum XOR Query

At each bit, greedily take the opposite child if it exists. This makes the current result bit 1, which is always better than 0 at a more significant position.

int max_xor(int x) {
    int u = 0, ans = 0;
    for (int b = LOG; b >= 0; --b) {
        int bit = (x >> b) & 1;
        int want = bit ^ 1;
        if (tr[u].child[want] != -1 && tr[tr[u].child[want]].cnt > 0) {
            ans |= 1 << b;
            u = tr[u].child[want];
        } else {
            u = tr[u].child[bit];
        }
    }
    return ans;
}

Deletion

Deletion is count decrement along the path. You do not need to physically remove nodes unless memory reuse matters.

void erase(int x) {
    int u = 0;
    tr[u].cnt--;
    for (int b = LOG; b >= 0; --b) {
        int bit = (x >> b) & 1;
        u = tr[u].child[bit];
        tr[u].cnt--;
    }
}

Queries with Constraints

For "maximize x ^ y where y <= m", sort array values and queries by m. Insert eligible values into the trie as the limit grows, then answer each query.

sort(nums.begin(), nums.end());
sort(queries.begin(), queries.end(),
     [](auto& a, auto& b){ return a.limit < b.limit; });

int ptr = 0;
for (auto& q : queries) {
    while (ptr < nums.size() && nums[ptr] <= q.limit) {
        trie.insert(nums[ptr++]);
    }
    answer[q.id] = ptr == 0 ? -1 : trie.max_xor(q.x);
}

Complexity and Memory

Practice Problems