Minimum XOR

You are given $q$ queries of two types:

1. $1X$: Append value $X$ into an array.
2. $2XK$: You are required to print the $K^{th}$ minimum XOR of $X$ with the current array.
   You have to make a new array whose $i^{th}$ element is current_array[i]${}^X$. Then sort it and print the $K^{th}$ element.

Example:

Input: q = 8, queries = {{1, 5}, {1, 3}, {1, 2}, {1, 9}, {2, 8, 3}, {1, 89}, {1, 56}, {2, 85, 5}}

Output:

11
92

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

//structure of the trie
struct Trienode
{
    Trienode *left;
    Trienode *right;
    int below = 0;
};

//function to insert the data into
//the trie
void insert(Trienode *head, long long element)
{
    Trienode *curr = head;
    for (long long i = 63; i >= 0; i--)
    {
        long long b = (element >> i) & 1;
        curr->below++;

        //if zero go for left side
        if (b == 0)
        {

            //if left does not exit
            //then create new node for left
            if (!curr->left)
            {
                curr->left = new Trienode();
            }

            //move to left of current node
            curr = curr->left;
        }

        //if not zero then go to
        //right side
        else
        {

            //if right does not exist
            //create new node for right
            if (!curr->right)
            {
                curr->right = new Trienode();
            }

            //move right of current node
            curr = curr->right;
        }
    }

    //update below
    curr->below++;
}

long long query(Trienode *head, long long x, long long k)
{
    Trienode *curr = head;
    long long ans = 0;
    for (long long i = 63; i >= 0; i--)
    {
        long long b = (x >> i) & 1;
        long long t = (1LL << i);
        long long res = 0;

        //if zero then go to left size
        if (b == 0)
        {

            //if current's left exist

            if (curr->left)
            {
                res = curr->left->below;
            }
            if (res >= k)
            {
                curr = curr->left;
            }

            //now move to right side
            else
            {
                ans += t;
                k -= res;
                if (!curr->right)
                {
                    curr->right = new Trienode();
                }
                curr = curr->right;
            }
        }

        //if not zero then go to right side
        else
        {
            if (curr->right)
            {
                res = curr->right->below;
            }
            if (res >= k)
            {
                curr = curr->right;
            }
            else
            {
                ans += t;
                k -= res;
                if (!curr->left)
                {
                    curr->left = new Trienode();
                }
                curr = curr->left;
            }
        }
    }
    return ans;
}

int main()
{

    Trienode *head = new Trienode();
    long long q = 8;

    vector<vector<long long>> queries = {{1, 5},
                                         {1, 3},
                                         {1, 2},
                                         {1, 9},
                                         {2, 8, 3},
                                         {1, 89},
                                         {1, 56},
                                         {2, 85, 5}};

    for (long long i = 0; i < q; i++)
    {
        long long c = queries[i][0];
        if (c == 1)
        {
            long long y = queries[i][1];
            insert(head, y);
        }
        else
        {
            long long x = queries[i][1];
            long long k = queries[i][2];

            cout << query(head, x, k) << "\n";
        }
    }
    return 0;
}