Maximum XOR of two numbers in an array

Given an array of non-negative integers of size N. Find the maximum possible XOR between two numbers present in the array.

• Time : O(n)
• Space : O(n)

struct Trie {
    Trie *next[2];
    bool eof = false;

    Trie() {
        memset(next, 0, sizeof next);
    }

    void insert(int n, int mask = 20) {
        if (mask == -1) eof = true;
        else {
            bool bit = n & (1 << mask);
            if (!next[bit]) next[bit] = new Trie();
            next[bit]->insert(n, mask - 1);
        }
    }

    int query(int n, int mask = 20) {
        if (mask == -1) return 0;
        bool bit = n & (1 << mask);
        if (next[!bit]) return (1 << mask) + next[!bit]->query(n, mask - 1);
        if (next[bit]) return next[bit]->query(n, mask - 1);
        return n & ((1 << (mask + 1)) - 1);
    }
};

class Solution {
public:
    int max_xor(int arr[], int n) {
        Trie* t = new Trie();
        t->insert(arr[0]);
        int res = 0;
        for(int i = 1; i < n; i++) {
            res = max(res, t->query(arr[i]));
            t->insert(arr[i]);
        }
        return res;
    }
};