Skip to content

1932. Merge BSTs to Create Single BST 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  TreeNode* canMerge(vector<TreeNode*>& trees) {
    unordered_map<int, TreeNode*> valToNode;  // {val: node}
    unordered_map<int, int> count;            // {val: freq}

    for (TreeNode* tree : trees) {
      valToNode[tree->val] = tree;
      ++count[tree->val];
      if (tree->left)
        ++count[tree->left->val];
      if (tree->right)
        ++count[tree->right->val];
    }

    for (TreeNode* tree : trees)
      if (count[tree->val] == 1) {
        if (isValidBST(tree, nullptr, nullptr, valToNode) &&
            valToNode.size() <= 1)
          return tree;
        return nullptr;
      }

    return nullptr;
  }

 private:
  bool isValidBST(TreeNode* tree, TreeNode* minNode, TreeNode* maxNode,
                  unordered_map<int, TreeNode*>& valToNode) {
    if (tree == nullptr)
      return true;
    if (minNode && tree->val <= minNode->val)
      return false;
    if (maxNode && tree->val >= maxNode->val)
      return false;
    if (!tree->left && !tree->right && valToNode.contains(tree->val)) {
      const int val = tree->val;
      tree->left = valToNode[val]->left;
      tree->right = valToNode[val]->right;
      valToNode.erase(val);
    }

    return isValidBST(tree->left, minNode, tree, valToNode) &&
           isValidBST(tree->right, tree, maxNode, valToNode);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public TreeNode canMerge(List<TreeNode> trees) {
    Map<Integer, TreeNode> valToNode = new HashMap<>(); // {val: node}
    Map<Integer, Integer> count = new HashMap<>();      // {val: freq}

    for (TreeNode tree : trees) {
      valToNode.put(tree.val, tree);
      count.merge(tree.val, 1, Integer::sum);
      if (tree.left != null)
        count.merge(tree.left.val, 1, Integer::sum);
      if (tree.right != null)
        count.merge(tree.right.val, 1, Integer::sum);
    }

    for (TreeNode tree : trees)
      if (count.get(tree.val) == 1) {
        if (isValidBST(tree, null, null, valToNode) && valToNode.size() <= 1)
          return tree;
        return null;
      }

    return null;
  }

  private boolean isValidBST(TreeNode tree, TreeNode minNode, TreeNode maxNode,
                             Map<Integer, TreeNode> valToNode) {
    if (tree == null)
      return true;
    if (minNode != null && tree.val <= minNode.val)
      return false;
    if (maxNode != null && tree.val >= maxNode.val)
      return false;
    if (tree.left == null && tree.right == null && valToNode.containsKey(tree.val)) {
      final int val = tree.val;
      tree.left = valToNode.get(val).left;
      tree.right = valToNode.get(val).right;
      valToNode.remove(val);
    }

    return                                                 //
        isValidBST(tree.left, minNode, tree, valToNode) && //
        isValidBST(tree.right, tree, maxNode, valToNode);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
  def canMerge(self, trees: list[TreeNode]) -> TreeNode | None:
    valToNode = {}  # {val: node}
    count = collections.Counter()  # {val: freq}

    for tree in trees:
      valToNode[tree.val] = tree
      count[tree.val] += 1
      if tree.left:
        count[tree.left.val] += 1
      if tree.right:
        count[tree.right.val] += 1

    def isValidBST(tree: TreeNode | None, minNode: TreeNode | None,
                   maxNode: TreeNode | None) -> bool:
      if not tree:
        return True
      if minNode and tree.val <= minNode.val:
        return False
      if maxNode and tree.val >= maxNode.val:
        return False
      if not tree.left and not tree.right and tree.val in valToNode:
        val = tree.val
        tree.left = valToNode[val].left
        tree.right = valToNode[val].right
        del valToNode[val]

      return isValidBST(
          tree.left, minNode, tree) and isValidBST(
          tree.right, tree, maxNode)

    for tree in trees:
      if count[tree.val] == 1:
        if isValidBST(tree, None, None) and len(valToNode) <= 1:
          return tree
        return None

    return None