1932. Merge BSTs to Create Single BST

Problem Description

You are given n binary search tree (BST) root nodes for n separate BSTs stored in an array called trees (0-indexed). Each BST in trees has at most 3 nodes, and no two roots have the same value. In one operation, you can:

Return the root of the resulting BST if it is possible to form a valid BST after performing n - 1 operations, or null if it is impossible to create a valid BST.

A BST (binary search tree) is a binary tree where each node satisfies the following property:

1. The value of any node to the left is lesser than the value of the current node.
2. The value of any node to the right is greater than the value of the current node.

A leaf is a node that has no children.

Example

Suppose we have the following BSTs:

1
2
3   2      3      5
4  / \      \    / \
5 1   3      4  3   6

One possible sequence of operations to create a valid BST is:

1. Merge the first and second BSTs:

1
2
3   2      
4  / \      
5 1   3      
6        \           
7         4

2. Merge the resulting BST with the third BST:

1
2
3       5
4      / \
5   2     6
6  / \
7 1   3
8      \
9       4

Since we were able to create a valid BST, the function returns the root node of the final BST, in this case, the node with value 5.

Solution Approach

The solution uses a depth-first search approach to build the final BST. Here are the steps of the algorithm:

1. Create two hash tables: valToNode to store each root node indexed by its value and count to store the frequencies of each value.
2. Iterate through the input trees, updating the hash tables.
3. For each tree in trees, check if the count of the tree's root value is 1. If it is, try to build a BST using a helper function isValidBST. If the resulting BST is valid and valToNode has at most one remaining entry, return the tree's root.
4. If no valid BST can be created, return null.

The helper function isValidBST performs a depth-first search to build a valid BST. It checks if the current tree node's value is within the specified range (minNode and maxNode) and whether the current node has children. If the current node has no children, it updates the node with the next node from valToNode and removes the entry from the hash table. The function continues checking the left and right subtrees and returns true if a valid BST is formed without any remaining entries in valToNode.

C++ Solution

1
2cpp
3#include <unordered_map>
4#include <vector>
5
6using namespace std;
7
8// Definition of TreeNode
9struct TreeNode {
10  int val;
11  TreeNode *left;
12  TreeNode *right;
13  TreeNode() : val(0), left(nullptr), right(nullptr) {}
14  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
15  TreeNode(int x, TreeNode *left, TreeNode *right)
16      : val(x), left(left), right(right) {}
17};
18
19class Solution {
20 public:
21  TreeNode* canMerge(vector<TreeNode*>& trees) {
22    unordered_map<int, TreeNode*> valToNode;  // {val: node}
23    unordered_map<int, int> count;            // {val: freq}
24
25    for (TreeNode* tree : trees) {
26      valToNode[tree->val] = tree;
27      ++count[tree->val];
28      if (tree->left)
29        ++count[tree->left->val];
30      if (tree->right)
31        ++count[tree->right->val];
32    }
33
34    for (TreeNode* tree : trees)
35      if (count[tree->val] == 1) {
36        if (isValidBST(tree, nullptr, nullptr, valToNode) &&
37            valToNode.size() <= 1)
38          return tree;
39        return nullptr;
40      }
41
42    return nullptr;
43  }
44
45 private:
46  bool isValidBST(TreeNode* tree, TreeNode* minNode, TreeNode* maxNode,
47                  unordered_map<int, TreeNode*>& valToNode) {
48    if (tree == nullptr)
49      return true;
50    if (minNode && tree->val <= minNode->val)
51      return false;
52    if (maxNode && tree->val >= maxNode->val)
53      return false;
54    if (!tree->left && !tree->right && valToNode.count(tree->val)) {
55      const int val = tree->val;
56      tree->left = valToNode[val]->left;
57      tree->right = valToNode[val]->right;
58      valToNode.erase(val);
59    }
60
61    return isValidBST(tree->left, minNode, tree, valToNode) &&
62           isValidBST(tree->right, tree, maxNode, valToNode);
63  }
64};

In this C++ solution, two unordered maps are used to store the root nodes and their frequencies. The main function canMerge and the helper function isValidBST operate on these hash tables and TreeNode objects to build and validate the final BST.

In summary, this solution combines smaller BSTs into a final valid BST by performing a depth-first search and making use of hash tables to keep track of root nodes and their frequencies.### Python Solution

1
2python
3from collections import defaultdict
4from typing import Optional
5
6# Definition of TreeNode
7class TreeNode:
8    def __init__(self, val=0, left=None, right=None):
9        self.val = val
10        self.left = left
11        self.right = right
12
13class Solution:
14    def canMerge(self, trees: list[TreeNode]) -> Optional[TreeNode]:
15        valToNode = {t.val: t for t in trees}  # {val: node}
16        count = defaultdict(int)               # {val: freq}
17
18        for tree in trees:
19            count[tree.val] += 1
20            if tree.left:
21                count[tree.left.val] += 1
22            if tree.right:
23                count[tree.right.val] += 1
24
25        for tree in trees:
26            if count[tree.val] == 1:
27                if self.isValidBST(tree, None, None, valToNode) and len(valToNode) <= 1:
28                    return tree
29                return None
30
31        return None
32
33    def isValidBST(self, tree: TreeNode, minNode: TreeNode, maxNode: TreeNode, valToNode: dict) -> bool:
34        if not tree:
35            return True
36        if minNode and tree.val <= minNode.val:
37            return False
38        if maxNode and tree.val >= maxNode.val:
39            return False
40        if not tree.left and not tree.right and tree.val in valToNode:
41            val = tree.val
42            tree.left = valToNode[val].left
43            tree.right = valToNode[val].right
44            del valToNode[val]
45
46        return self.isValidBST(tree.left, minNode, tree, valToNode) and \
47               self.isValidBST(tree.right, tree, maxNode, valToNode)

The Python solution is very similar to the C++ solution, utilizing a dictionary to store the root nodes and their frequencies, and a defaultdict for the count. The main function canMerge and the helper function isValidBST work together to create and validate the final BST.

Java Solution

1
2java
3import java.util.HashMap;
4import java.util.List;
5import java.util.Map;
6
7// Definition of TreeNode
8class TreeNode {
9    int val;
10    TreeNode left;
11    TreeNode right;
12    TreeNode() {}
13    TreeNode(int val) { this.val = val; }
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21public class Solution {
22    public TreeNode canMerge(List<TreeNode> trees) {
23        Map<Integer, TreeNode> valToNode = new HashMap<>();  // {val: node}
24        Map<Integer, Integer> count = new HashMap<>();       // {val: freq}
25
26        for (TreeNode tree : trees) {
27            valToNode.put(tree.val, tree);
28            count.put(tree.val, count.getOrDefault(tree.val, 0) + 1);
29            if (tree.left != null)
30                count.put(tree.left.val, count.getOrDefault(tree.left.val, 0) + 1);
31            if (tree.right != null)
32                count.put(tree.right.val, count.getOrDefault(tree.right.val, 0) + 1);
33        }
34
35        for (TreeNode tree : trees)
36            if (count.get(tree.val) == 1) {
37                if (isValidBST(tree, null, null, valToNode) && valToNode.size() <= 1)
38                    return tree;
39                return null;
40            }
41
42        return null;
43    }
44
45    private boolean isValidBST(TreeNode tree, TreeNode minNode, TreeNode maxNode, Map<Integer, TreeNode> valToNode) {
46        if (tree == null)
47            return true;
48        if (minNode != null && tree.val <= minNode.val)
49            return false;
50        if (maxNode != null && tree.val >= maxNode.val)
51            return false;
52        if (tree.left == null && tree.right == null && valToNode.containsKey(tree.val)) {
53            int val = tree.val;
54            tree.left = valToNode.get(val).left;
55            tree.right = valToNode.get(val).right;
56            valToNode.remove(val);
57        }
58
59        return isValidBST(tree.left, minNode, tree, valToNode) &&
60               isValidBST(tree.right, tree, maxNode, valToNode);
61    }
62}

The Java solution is also similar to both the C++ and Python solutions, utilizing a HashMap to store the root nodes and their frequencies. The main function canMerge and the helper function isValidBST work on these hash tables and TreeNode objects to build and validate the resulting BST.

Now, we have provided solutions in three languages, Python, Java, and C++, using the same depth-first search approach and making use of hash tables to keep track of root nodes and their frequencies.

Solution Implementation