Min XOR Value

Given an array of N integers, find the pair of integers in the array which have minimum XOR value. Report the minimum XOR value.

Examples :
Input
0 2 5 7
Output
2 (0 XOR 2)
Input
0 4 7 9
Output
3 (4 XOR 7)

Constraints:
2 <= N <= 100 000
0 <= A[i] <= 1 000 000 000

Method1:

We sort the array and then compare the neighbors because the min value can only exist between neighbors.

Solution1:

Time: O(nlogn)
Space: O(1)

public class Solution {
    public int findMinXor(ArrayList<Integer> A) {
        Collections.sort(A);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < A.size() - 1; i ++) {
            int a = A.get(i);
            int b = A.get(i + 1);
            min = Math.min(min, a ^ b);
        }
        return min;
    }
}

Method2:

Use Trie.

Solution2:

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

public class Solution {
    static class TrieNode {
        int value;
        TrieNode[] children = new TrieNode[2];
        
        public TrieNode() {
            value = 0;
            children[0] = null;
            children[1] = null;
        }
    }
    
    static class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void insert(int key) {
            TrieNode curr = root;
            for (int i = 31; i >= 0; i --) {
                int currentBit = (key & (1 << i)) >= 1 ? 1 : 0;
                if (curr.children[currentBit] == null) {
                    curr.children[currentBit] = new TrieNode();
                }
                curr = curr.children[currentBit];
            }
            curr.value = key;
        }
        
        public int minXOR(int key) {
            TrieNode curr = root;
            for (int i = 31; i >= 0; i --) {
                int currentBit = (key & (1 << i)) >= 1 ? 1 : 0;
                if (curr.children[currentBit] != null) {
                    curr = curr.children[currentBit];
                } else if (curr.children[1 - currentBit] != null) {
                    curr = curr.children[1 - currentBit];
                }
            }
            return curr.value ^ key;            
        }
    }
    
    public int findMinXor(ArrayList<Integer> A) {
        Trie trie = new Trie();
        trie.insert(A.get(0));
        int minXor = Integer.MAX_VALUE;
        for (int i = 1; i < A.size(); i ++) {
            minXor = Math.min(minXor, trie.minXOR(A.get(i)));
            trie.insert(A.get(i));
        }
        return minXor;
    }
}