# Trie Based Approach in C++

#1
``````struct Node
{
Node *next[2];

Node()
{
next[0]=NULL;
next[1]=NULL;
}
};
void insert(int A,Node* root)
{
Node* temp = root;
for(int i=31;i>=0;i--)
{
int bit = A>>i & 1;
if(temp->next[bit] == NULL)
temp->next[bit] = new Node();
temp = temp->next[bit];
}
return;
}
int findxor(vector<int> &B,Node* root)
{
Node* temp;
int finalMax=0;
for(int i=0;i<B.size();i++)
{   temp = root;
int currResult=0;
for(int j=31;j>=0;j--)
{
int oppBit = ((B[i]>>j) & 1) ? 0 : 1; // If bit is 1 then oppBit (opposite bit) is 0 and vice-versa
if(temp->next[oppBit]!=NULL)
{
currResult = currResult<<1;
currResult = currResult|1;
temp = temp->next[oppBit];
}
else
{
currResult = currResult<<1;
currResult = currResult|0; // This is not neccessary to write
temp = temp->next[oppBit?0:1]; // Opposite Bit is not present so go to other bit
}
}
if(currResult>finalMax)
finalMax=currResult;
}
return finalMax;
}
int Solution::solve(vector<int> &A, vector<int> &B) {

Node* root = new Node(); // Creating root node for trie
for(int i=0;i<A.size();i++) // Binary representation of each element of array A is inserted in to Trie
insert(A[i],root);
int ans = findxor(B,root); // For Binary representation of each element of array B is compared in Trie
return ans;
}``````