Python | Easy to understand | Trie with Insert and Search
Apporach\nTo find out max XOR of any given two numbers in the array, essentially we need to\n1. convert the number into binary format\n2. for each bit, try to m
**Apporach**\nTo find out max `XOR` of any given two numbers in the array, essentially we need to\n1. convert the number into binary format\n2. for each bit, try to maximize the output of `XOR`, which is finding the opposite bit and calculate the max result\n\t* Think this as BFS, for each level, we compute a result and move to next level\n3. do this every number in the array and return the max result\n\n\n**Implementation**\n1. Build a trie like you would do in all another trie problems\n2. Add one more method `search` in the trie\n\t* `search` method here does one thing: for any given binary format string, it checks at the level, if there is an opposite bit that we could use to compute the XOR result.\n\n\nOne small optimization:\n* if you try to format every number in 32 bit format, it will Timeout for the last input. You do not need to `zfill` 32 bits, just find largest number in the array and use that length to do the format.\n\n\n```\n\nfrom collections import defaultdict\n\nclass TrieNode:\n    def __init__(self):\n        self.children = defaultdict(TrieNode)\n        self.val = 0\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n    \n    def insert(self, binary):\n        cur = self.root\n        for char in binary:\n            cur = cur.children[int(char)]\n    \n    def search(self, binary) -> int:\n        result = 0\n        cur = self.root\n        for char in binary:\n            opposite = 1 - int(char)\n            if opposite in cur.children:\n                result = (result << 1) | 1\n                cur = cur.children[opposite]\n            else:\n                result = (result << 1)\n                cur = cur.children[int(char)]\n        return result\n\nclass Solution:\n    def findMaximumXOR(self, nums: List[int]) -> int:\n        trie = Trie()\n        result = float(\'-inf\')\n        maxLen = len(bin(max(nums))[2:]) # format binary string in length of  max num\n        for num in nums:\n            key = bin(num)[2:].zfill(maxLen)\n            trie.insert(key)\n            result = max(result, trie.search(key))\n        return result\n```
['Trie', 'Python']