1932. Merge BSTs to Create Single BST - Leetcode Solution

Problem Description

The "Merge BSTs to Create Single BST" problem asks you to merge multiple binary search trees (BSTs) into a single, valid BST. You are given a list of BSTs, each with unique node values, and you must combine them so that the resulting tree is also a valid BST and contains all the nodes from the input trees, without duplicating or omitting any node.

Each input BST is represented by its root node in the list trees.
Each node value is unique across all trees.
You must use all nodes exactly once (no duplicates or omissions).
The final merged tree must be a valid BST.
If it is not possible to merge all trees into a single BST, return null.
There is at most one valid way to merge all the trees.

Thought Process

At first, you might think about brute-forcing all possible ways to attach the trees together, but this quickly becomes infeasible as the number of trees grows. Instead, let's look for a more systematic approach:

Since all values are unique, each node can appear only once in the final tree.
For a valid BST merge, a tree can only be attached at a leaf node (i.e., a node with no children in the position you want to attach).
If a node's value matches the root of another tree, we can try to replace that leaf with the corresponding tree.
We need to ensure that after merging, the BST property holds everywhere.
We must also prevent cycles or duplicate use of any node.

The challenge is to efficiently identify where to "plug in" each tree and to verify that the merged result is still a BST.

Solution Approach

To solve the problem efficiently, we can use the following step-by-step strategy:

Map all roots: Build a hash map from root value to tree root for all input trees. This allows O(1) lookup to find a tree by its value.
Count all child node values: For each tree, count all left and right child values. This helps us identify which trees are "roots" in the final tree (since their root value is never a child elsewhere).
Find the global root: The root of the final BST must be the one whose value is not found as any child value. If there is more than one such tree, or none, merging is impossible.
Attach subtrees: Traverse the main root. Whenever you encounter a leaf node whose value matches another tree's root, replace that leaf with the corresponding tree root (i.e., "plug in" the subtree).
Check BST validity: After merging, ensure the final tree is a valid BST and that all nodes are used exactly once.

This approach leverages hash maps for fast lookup and ensures that the merge process is unambiguous and efficient.

Example Walkthrough

Suppose you are given these three BSTs:

Tree 1: 2 (left: 1, right: 3)
Tree 2: 5 (left: 4)
Tree 3: 3 (right: 6)

Map all roots: {2: Tree1, 5: Tree2, 3: Tree3}
Count all child node values: Children are 1, 3 (from Tree1), 4 (from Tree2), 6 (from Tree3)
Find the global root: Roots are 2, 3, 5. Only 2 and 5 are not children. But 2 is the only one that is not a child anywhere.
Attach subtrees: Tree1's right child is 3, which matches Tree3's root, so we replace Tree1's right child with Tree3. Tree3's right child is 6 and has no matching tree, so we leave it.
Check BST validity: The merged tree is:
- 2
- ↙️ 1
- ↘️ 3
- ↘️ 6
All nodes are used once, and the BST property holds.

Time and Space Complexity

Brute-force approach: Trying all possible ways to attach trees is exponential in the number of trees (O(k!)), which is infeasible.
Optimized approach:
- Building maps and counting child values: O(n), where n is the total number of nodes.
- Merging the trees: Each node is visited once, so O(n).
- Checking BST validity: O(n).
- Total time complexity: O(n).
- Space complexity: O(n) for maps and to store the merged tree.

Summary

This problem is elegantly solved by recognizing that the unique root can be found by exclusion, and that each tree can only be attached at a leaf with a matching value. By using hash maps for fast lookup and careful traversal, we ensure all nodes are used once and the BST property is preserved. The process is efficient and scales well, as each node is processed only once.

Code Implementation


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def canMerge(self, trees):
        root_map = {tree.val: tree for tree in trees}
        child_vals = set()
        for tree in trees:
            if tree.left:
                child_vals.add(tree.left.val)
            if tree.right:
                child_vals.add(tree.right.val)
        # Find the root that is not a child
        roots = [tree for tree in trees if tree.val not in child_vals]
        if len(roots) != 1:
            return None
        root = roots[0]
        used = set()
        def merge(node, min_val, max_val):
            if not node:
                return True
            if not (min_val < node.val < max_val):
                return False
            if node.val in used:
                return False
            used.add(node.val)
            # If node is a leaf and can be replaced
            if not node.left and not node.right and node.val in root_map and node is not root_map[node.val]:
                subtree = root_map[node.val]
                node.left = subtree.left
                node.right = subtree.right
            return merge(node.left, min_val, node.val) and merge(node.right, node.val, max_val)
        if not merge(root, float('-inf'), float('inf')):
            return None
        if len(used) != sum(self.countNodes(tree) for tree in trees):
            return None
        return root

    def countNodes(self, root):
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map rootMap;
    unordered_set used;
    int nodeCount(TreeNode* root) {
        if (!root) return 0;
        return 1 + nodeCount(root->left) + nodeCount(root->right);
    }
    bool merge(TreeNode* node, long minVal, long maxVal, TreeNode* globalRoot) {
        if (!node) return true;
        if (!(minVal < node->val && node->val < maxVal)) return false;
        if (used.count(node->val)) return false;
        used.insert(node->val);
        if (!node->left && !node->right && rootMap.count(node->val) && node != rootMap[node->val]) {
            TreeNode* subtree = rootMap[node->val];
            node->left = subtree->left;
            node->right = subtree->right;
        }
        return merge(node->left, minVal, node->val, globalRoot) && merge(node->right, node->val, maxVal, globalRoot);
    }
    TreeNode* canMerge(vector& trees) {
        rootMap.clear();
        used.clear();
        unordered_set childVals;
        int totalNodes = 0;
        for (auto tree : trees) {
            rootMap[tree->val] = tree;
        }
        for (auto tree : trees) {
            if (tree->left) childVals.insert(tree->left->val);
            if (tree->right) childVals.insert(tree->right->val);
        }
        vector roots;
        for (auto tree : trees) {
            if (!childVals.count(tree->val)) roots.push_back(tree);
        }
        if (roots.size() != 1) return nullptr;
        TreeNode* root = roots[0];
        for (auto tree : trees) totalNodes += nodeCount(tree);
        if (!merge(root, LONG_MIN, LONG_MAX, root)) return nullptr;
        if (used.size() != totalNodes) return nullptr;
        return root;
    }
};


// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    Map rootMap = new HashMap<>();
    Set used = new HashSet<>();
    int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    boolean merge(TreeNode node, long minVal, long maxVal, TreeNode globalRoot) {
        if (node == null) return true;
        if (!(minVal < node.val && node.val < maxVal)) return false;
        if (used.contains(node.val)) return false;
        used.add(node.val);
        if (node.left == null && node.right == null && rootMap.containsKey(node.val) && node != rootMap.get(node.val)) {
            TreeNode subtree = rootMap.get(node.val);
            node.left = subtree.left;
            node.right = subtree.right;
        }
        return merge(node.left, minVal, node.val, globalRoot) && merge(node.right, node.val, maxVal, globalRoot);
    }
    public TreeNode canMerge(List trees) {
        rootMap.clear();
        used.clear();
        Set childVals = new HashSet<>();
        int totalNodes = 0;
        for (TreeNode tree : trees) {
            rootMap.put(tree.val, tree);
        }
        for (TreeNode tree : trees) {
            if (tree.left != null) childVals.add(tree.left.val);
            if (tree.right != null) childVals.add(tree.right.val);
        }
        List roots = new ArrayList<>();
        for (TreeNode tree : trees) {
            if (!childVals.contains(tree.val)) roots.add(tree);
        }
        if (roots.size() != 1) return null;
        TreeNode root = roots.get(0);
        for (TreeNode tree : trees) totalNodes += countNodes(tree);
        if (!merge(root, Long.MIN_VALUE, Long.MAX_VALUE, root)) return null;
        if (used.size() != totalNodes) return null;
        return root;
    }
}


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode[]} trees
 * @return {TreeNode}
 */
var canMerge = function(trees) {
    const rootMap = new Map();
    const childVals = new Set();
    for (const tree of trees) {
        rootMap.set(tree.val, tree);
    }
    for (const tree of trees) {
        if (tree.left) childVals.add(tree.left.val);
        if (tree.right) childVals.add(tree.right.val);
    }
    const roots = trees.filter(tree => !childVals.has(tree.val));
    if (roots.length !== 1) return null;
    const root = roots[0];
    let used = new Set();
    function countNodes(node) {
        if (!node) return 0;
        return 1 + countNodes(node.left) + countNodes(node.right);
    }
    function merge(node, minVal, maxVal) {
        if (!node) return true;
        if (!(minVal < node.val && node.val < maxVal)) return false;
        if (used.has(node.val)) return false;
        used.add(node.val);
        if (!node.left && !node.right && rootMap.has(node.val) && node !== rootMap.get(node.val)) {
            const subtree = rootMap.get(node.val);
            node.left = subtree.left;
            node.right = subtree.right;
        }
        return merge(node.left, minVal, node.val) && merge(node.right, node.val, maxVal);
    }
    let totalNodes = 0;
    for (const tree of trees) totalNodes += countNodes(tree);
    if (!merge(root, -Infinity, Infinity)) return null;
    if (used.size !== totalNodes) return null;
    return root;
};

AlgoMap.io

Want Help Cracking FAANG?