# C++ Trie 69ms beats 85%

• ``````class Solution {
public:
class TreeNode {
public:
TreeNode* next[2];
TreeNode () {next[0] = NULL; next[1] = NULL;};
};
TreeNode* buildTree(vector<int>& nums) {
TreeNode* root = new TreeNode(), *cur;
int n = nums.size();
for (int i = 0; i < n; i++) {
int num = nums[i];
cur = root;
for (int j = 31; j >= 0; j--) {
int index = ((num >> j) & 1);
if (cur->next[index] ==  NULL)
cur->next[index] = new TreeNode();
cur = cur->next[index];
}
}
return root;
}

int helper(TreeNode* cur, int num) {
int res = 0;
for (int i = 31; i >= 0; i--) {
int index = ((num >> i) & 1) ? 0 : 1;
if (cur->next[index]) {
res <<= 1;
res |= 1;
cur = cur->next[index];
} else {
res <<= 1;
res |= 0;
cur = cur->next[index ? 0 : 1];
}
}
return res;
}

int findMaximumXOR(vector<int>& nums) {
int res = 0;
TreeNode* root = buildTree(nums);

for (auto i : nums) {
res = max(res, helper(root, i));
}

return res;
}
};
``````

• @yong.cao.7731 A few lines shorter for the method "helper":

``````    int helper(TreeNode* cur, int num) {
int res = 0;
for (int i = 31; i >= 0; i--) {
int index = (num >> i) & 1;
if (cur->next[index ^ 1]) {
res += 1 << i;
cur = cur->next[index ^ 1];
} else {
cur = cur->next[index];
}
}
return res;
}``````

• Thank you for sharing the brilliant answer! But I think the maximum height of the tree is only 31 instead of 32, as nums[i]< 2^31.
So the code

``````for (int j = 31; j >= 0; j--) {
//...
}
``````

actually could be

``````for (int j = 30; j >= 0; j--) {
//...
}
``````

• This post is deleted!

• @yaopiupiupiu Yes, you are correct. Thanks

• can somebody help understand how trie is helping in this problem?

• @sha256pki just traverse every input num and try to find a number x from trie tree, which can help to max num^x

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.