LeetCode 1932: Merge BSTs to Create Single BST Solution

Master LeetCode problem 1932 (Merge BSTs to Create Single BST), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1932. Merge BSTs to Create Single BST

Hard

Hash Table Binary Search Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To merge the given BSTs into a single valid BST, we can simulate the process by iteratively merging BSTs based on the values at the leaves and roots of the trees. We can use a recursive approach to merge the BSTs. The key idea is to find a leaf node in one tree whose value matches with the root of another tree, then merge the two trees by replacing the leaf node with the entire tree rooted at the other tree's root.

Create a map to store the root values of the trees for quick access.
Initialize a set to keep track of the visited indices of trees.
Iterate through the trees and recursively merge the BSTs by finding a leaf node value that matches the root value of another tree.
Perform the merge operation by updating the tree structure and removing the merged tree from the list.
Repeat the merging process until a valid BST is formed or until it is impossible to create a valid BST.

Time Complexity: O(n^2) - Since we potentially need to iterate over all pairs of trees in the worst case scenario. Space Complexity: O(n) - Additional space is used for the map, set, and recursive stack.

Solution Code

class Solution {
    public TreeNode mergeBSTs(TreeNode[] trees) {
        Map<Integer, TreeNode> rootMap = new HashMap<>();
        Set<Integer> visited = new HashSet<>();
        
        for (TreeNode root : trees) {
            rootMap.put(root.val, root);
        }
        
        while (rootMap.size() > 1) {
            boolean merged = false;
            for (int i = 0; i < trees.length; i++) {
                if (visited.contains(i)) continue;
                TreeNode tree = trees[i];
                TreeNode leaf = findLeaf(tree);
                if (rootMap.containsKey(leaf.val)) {
                    TreeNode root = rootMap.get(leaf.val);
                    mergeTrees(tree, root);
                    visited.add(i);
                    rootMap.remove(root.val);
                    merged = true;
                }
            }
            
            if (!merged) break;
        }
        
        return rootMap.size() == 1 ? rootMap.entrySet().iterator().next().getValue() : null;
    }
    
    private TreeNode findLeaf(TreeNode node) {
        if (node.left == null && node.right == null) {
            return node;
        }
        if (node.left != null) {
            return findLeaf(node.left);
        } else {
            return findLeaf(node.right);
        }
    }
    
    private void mergeTrees(TreeNode tree, TreeNode root) {
        if (tree.left != null) {
            mergeTrees(tree.left, root);
        } else {
            tree.left = root;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1932 (Merge BSTs to Create Single BST)?

This page provides optimized solutions for LeetCode problem 1932 (Merge BSTs to Create Single BST) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1932 (Merge BSTs to Create Single BST)?

The time complexity for LeetCode 1932 (Merge BSTs to Create Single BST) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1932 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1932 in Java, C++, or Python.

Back to LeetCode Solutions