We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Merge BSTs to Create Single BST

Number: 2060

Difficulty: Hard

Paid? No

Companies: Microsoft, Bloomberg

Problem Description

You are given n separate BSTs (binary search trees), each with at most 3 nodes. In one operation, you can merge two BSTs by replacing a leaf node in one tree with another tree whose root has the same value as that leaf. After exactly n - 1 merge operations, you need to obtain one valid BST. A valid BST must satisfy that every left child is strictly less than its parent and every right child is strictly greater than its parent. Return the root of the resulting BST if possible; otherwise, return null.

Key Insights

  • Identify the unique tree that should be the final root. It will be the only tree whose root value does not appear as a leaf in any other tree.
  • Use a hash map (dictionary) to map each tree’s root value to its tree.
  • Merge operations: For each leaf node matching another tree's root value, attach the tree and remove it from the collection.
  • While performing merges, carefully keep track of BST constraints by validating the boundaries of each subtree.
  • After merging, perform an in-depth DFS traversal to ensure the final tree satisfies the BST properties.
  • Ensure that exactly n - 1 merge operations have been applied—i.e., all trees are merged into one.

Space and Time Complexity

Time Complexity: O(n) – We process each tree and perform DFS validations over a total of O(n) nodes. Space Complexity: O(n) – Additional space is needed for the hash map and recursion stack for DFS.

Solution

The solution involves three main steps:

  1. Identify the candidate for the final root tree by mapping every tree's root and tracking which values appear as leaves. The candidate is the one whose root does not appear as any leaf value in all trees.
  2. Recursively merge trees using DFS. When encountering a leaf node, if it matches a tree from the hash map, replace that leaf with that subtree and continue the process.
  3. After merging all trees, perform a DFS (or similar traversal) to validate the BST properties of the complete tree by using bounds to check each subtree. A hash table is used to quickly look up candidate subtrees for merging, and DFS is used both for the merge process (to locate valid leaves) and for validating the final BST property.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# 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):
        # Map each tree's root value to the corresponding tree
        roots = {tree.val: tree for tree in trees}
        # Set to track all leaf values that appear in trees
        leafValues = set()
        
        # Gather all leaf nodes from each tree
        for tree in trees:
            if tree.left:
                leafValues.add(tree.left.val)
            if tree.right:
                leafValues.add(tree.right.val)
        
        # Identify candidate tree whose root is not a leaf in any other tree.
        candidate = None
        for tree in trees:
            if tree.val not in leafValues:
                candidate = tree
                break
        # If no candidate found, it's impossible to merge into one BST.
        if candidate is None:
            return None
        
        # Remove candidate's root from roots map because it will be our main tree.
        del roots[candidate.val]
        
        # Recursive merge: traverse current tree, if a leaf node matches a tree's root in map, attach it.
        def dfs(node, low, high):
            if node is None:
                return True
            # Ensure the node value is within allowed bounds.
            if not (low < node.val < high):
                return False
            # Check if current node is a leaf and can be merged.
            if node.left is None and node.right is None and node.val in roots:
                # Attach the tree whose root is node.val.
                subTree = roots.pop(node.val)
                # Merge by replacing current leaf node with the subtree.
                node.left = subTree.left
                node.right = subTree.right
            # Continue recursively for left and right subtrees with updated bounds.
            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
        
        # Perform DFS merge and check BST validity.
        if not dfs(candidate, float("-inf"), float("inf")):
            return None
        # If all trees were not merged, then merge is incomplete.
        if roots:
            return None
        return candidate
← Back to All Questions