Merge BSTs to Create Single BST LeetCode solution in C++

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  TreeNode *canMerge(vector<TreeNode *> &trees) {
16
    // store the leaves of every node
17

18
    unordered_map<int, TreeNode *> mp;
19

20
    // store the current min and current max nodes in the current tree
21
    unordered_map<TreeNode *, pair<int, int>> mini;
22
    for (int i = 0; i < trees.size(); i++) {
23
      pair<int, int> ans = {trees[i]->val, trees[i]->val};
24
      if (trees[i]->left) {
25
        mp[trees[i]->left->val] = {trees[i]};
26
        ans.first = trees[i]->left->val;
27
      }
28
      if (trees[i]->right) {
29
        mp[trees[i]->right->val] = trees[i];
30
        ans.second = trees[i]->right->val;
31
      }
32
      mini[trees[i]] = ans;
33
    }
34

35
    // store the number of merging operations we will be doing
36
    int count = 0;
37
    int rootCount = 0;
38
    TreeNode *root = NULL;
39
    // now for every node get the root
40
    for (int i = 0; i < trees.size(); i++) {
41
      // if the current tree can be merged into some other tree
42
      if (mp.find(trees[i]->val) != mp.end()) {
43
        count++;
44
        // merge them
45
        TreeNode *parent = mp[trees[i]->val];
46
        if (trees[i]->val < parent->val) {
47
          // left child
48

49
          // if the maximum of the current sub tree is greater than the parent
50
          // value then return NULL
51
          if (parent->val <= mini[trees[i]].second) return NULL;
52
          // change the minimum value of the parent tree to the current min
53
          // value of the tree
54
          mini[parent].first = mini[trees[i]].first;
55
          // merge the trees
56
          parent->left = trees[i];
57
        } else if (trees[i]->val > parent->val) {
58
          // right child
59

60
          // if the minimum of the current tree is lesser than the parent value
61
          // we cannot merge
62
          // so return NULL
63
          if (parent->val >= mini[trees[i]].first) return NULL;
64

65
          // change the parent tree maximum to the current tree maximum
66
          mini[parent].second = mini[trees[i]].second;
67
          // merge the trees
68
          parent->right = trees[i];
69
        }
70
        // erase the current tree value
71
        mp.erase(trees[i]->val);
72
      } else {
73
        // it has no other tree to merge
74
        // it is the root node we should return
75
        if (rootCount == 1)
76
          return NULL;
77
        else {
78
          rootCount++;
79
          root = trees[i];
80
        }
81
      }
82
    }
83
    // if we are not able to merge all trees return NULL
84
    if (count != trees.size() - 1) return NULL;
85
    return root;
86
  }
87
};