Python O(N) trie -- with explanation
I found the other solutions in this discussion thread to be very confusing, so I\'ll do my best to explain the solution.  I\'ll skip the code implementing the t
I found the other solutions in this discussion thread to be very confusing, so I\'ll do my best to explain the solution.  I\'ll skip the code implementing the trie because you can search the line.   Here\'s what we want to do: \n\n1) Insert the binary representation of a number into the trie.  Here, we insert from most significant bit to least significant bit, meaning the first node in the trie is the MSB and so on..\n\n2) Everytime we insert a number (let\'s call this number A), we want to traverse the trie a second time and go the opposite way as A\'s binary representation as much as possible.  It\'s important that our trie elements were entered from MSB to LSB because this will maximize the differences as we traverse down the tree.  \n\n3) Find the node that diverges most with A and then return the XOR of these two numbers so we can update the max XOR.\n\n\n```\nclass Trie:\n    \n    def __init__(self):\n        self.root = TrieNode()\n    \n    def insert(self, word, val):\n        curr = self.root\n        for i in range(len(word)):\n            bit = word[i]\n            if bit not in curr.children:\n                curr.children[bit] = TrieNode()\n            curr = curr.children[bit]\n        curr.isEnd = True\n        curr.value = val\n    \n    def search(self, word, target):\n        curr = self.root\n        for i in range(len(word)):\n            bit = word[i]\n            \n            if bit == \'1\' and curr.children.get(\'0\'):\n                curr = curr.children[\'0\']\n            elif bit == \'0\' and curr.children.get(\'1\'):\n                curr = curr.children[\'1\']\n            elif curr.children.get(bit):\n                curr = curr.children[bit]\n            else:\n                break\n                \n        return target^curr.value\n            \n            \nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.isEnd = False\n        self.value = 0\n    \n\nclass Solution(object):\n    def findMaximumXOR(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        self.trie = Trie()\n        max_xor = -2**(32)\n        \n        for i in nums:\n            binary_string = (bin(i)[2:]).zfill(31)\n            self.trie.insert(binary_string, i)\n            max_xor = max(max_xor, self.trie.search(binary_string, i))\n        \n        return max_xor\n\n```
[]