C++ Trie - with clear comments to help understand why Trie works
\nclass Solution {\npublic:\n    struct Node {\n      Node* zero_bit = nullptr;\n      Node* one_bit = nullptr;\n    };\n    Node* root = new Node();\n  \n    /
```\nclass Solution {\npublic:\n    struct Node {\n      Node* zero_bit = nullptr;\n      Node* one_bit = nullptr;\n    };\n    Node* root = new Node();\n  \n    // All Trie represent incremental pieces of a final value (chars -> string)\n    // For an int, the incremental piece is a bit, so we will make Trie of bit-string\n    // The Trie should always be accessed in chunks of 32 nodes (including root), so no concept\n    // of intermediate versus final result (prefix vs word) is needed.\n    void insert(const int& num) {\n      Node* ptr = root;\n      // Access all the bits MSB to LSB meaning index 31 to index 0\n      for (int i = 31; i >= 0; i--) {\n        if ((num >> i) & 1) { // bit in position i is a 1. Add to Trie if missing and move that way\n          if (!ptr->one_bit) {\n            ptr->one_bit = new Node();\n          }\n          ptr = ptr->one_bit;\n        } else { // bit in position i is a 0. Add to Trie if missing and move that way\n          if (!ptr->zero_bit) {\n            ptr->zero_bit = new Node();\n          }\n          ptr = ptr->zero_bit;\n        }\n      }\n    }\n  \n    // For the input number, for each bit, search the Trie bits that yield the most\n    // bit-wise XOR as 1. Based on the rule of XOR:\n    // 0 XOR 1 = 1\n    // 1 XOR 0 = 1\n    // Effectively it means, for the given bit, take the opposite child\n    // If you couldn\'t take the child you wanted, the bit-wise XOR result is 0, so continue\n    // If you can take the child you want, then bit-wise XOR result is 1, so |= (1 << i) into a temp result.\n\t// (pow(2,i) does the same but keeps things as int rather than bit-manipulations).\n\t// This is to keep track of the output bit-wise XOR as you visit each child.\n    int getMaxXOR(const int& num) {\n      Node* ptr = root;\n      int temp = 0;\n      for (int i = 31; i >= 0; i--) {\n        if ((num >> i) & 1) {\n          if (ptr->zero_bit) {\n            temp += pow(2,i);\n            ptr = ptr->zero_bit;\n          } else {\n            ptr = ptr->one_bit;\n          }\n        } else {\n          if (ptr->one_bit) {\n            temp += pow(2,i);\n            ptr = ptr->one_bit;\n          } else {\n            ptr = ptr->zero_bit;\n          }\n        }\n      }\n      return temp;\n    }\n  \n    int findMaximumXOR(vector<int>& nums) {\n      for (const int &i : nums) {\n        insert(i);\n      }\n      int max = 0;\n      for (const int &i : nums) {\n        int ret = getMaxXOR(i);\n        if (ret > max) max = ret;\n      }\n      return max;\n    }\n};\n```
[]