# JAVA, 50ms, DFS traversal, O(n)

• Construct a bst, and traversse.
Each call of dfs visits 2 nodes (could be the same), there are n leaves, and depth is 31, so in total there are less than 31n nodes, each node is visited only once, so O(n).

``````class TreeNode {
TreeNode left, right;
}
public int findMaximumXOR(int[] nums) {
TreeNode root = new TreeNode();
for (int num : nums) {
TreeNode p = root;
for (int i = 0; i < 31; ++i) {
if ((num & 1 << 30 - i) == 0) {
if (p.left == null) p.left = new TreeNode();
p = p.left;
} else {
if (p.right == null) p.right = new TreeNode();
p = p.right;
}
}
}
return dfs(root, root, 0);
}
int dfs(TreeNode n1, TreeNode n2, int level) {
if (level == 31) return 0;
if (n1.left == null || n1.right == null || n2.left == null || n2.right == null) {
if (n1.left != null && n2.right != null) {
return (1 << 30 - level) + dfs(n1.left, n2.right, level + 1);
} else if (n1.right != null && n2.left != null) {
return (1 << 30 - level) + dfs(n1.right, n2.left, level + 1);
} else if (n1.left != null) {
return dfs(n1.left, n2.left, level + 1);
} else {
return dfs(n1.right, n2.right, level + 1);
}
} else {
return (1 << 30 - level) + Math.max(dfs(n1.left, n2.right, level + 1), dfs(n1.right, n2.left, level + 1));
}
}
``````

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