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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Merge BSTs to Create Single BST

Difficulty: Hard

Problem Description

You are given n BST (binary search tree) root nodes for n separate BSTs stored in an array 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:

  • Select two distinct indices i and j such that the value stored at one of the leaves of trees[i] is equal to the root value of trees[j].
  • Replace the leaf node in trees[i] with trees[j].
  • Remove trees[j] from trees.

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.

Key Insights

  • A valid BST must maintain the property that every node in the left subtree has a value strictly less than the node's value, and every node in the right subtree has a value strictly greater.
  • The merging operation allows for a limited number of merges due to the leaf node restriction, which can quickly lead to invalid BST configurations.
  • Since each BST can have at most 3 nodes, the merging process is relatively straightforward but needs careful value checking to maintain the BST properties.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of trees, as we may need to check each tree multiple times during the merging process.

Space Complexity: O(n) - we may need to maintain additional structures to keep track of the values and their relationships during merging.

Solution

To solve this problem, we can use a Hash Table (or dictionary) to keep track of potential leaf nodes and their corresponding trees. The approach involves:

  1. Iterating through the list of trees and storing the leaves of each tree in a Hash Table.
  2. For each tree, check if any of its leaves can be replaced by the root of another tree.
  3. Maintain the properties of the BST by ensuring that all merged trees remain valid at each step.
  4. If it's possible to merge all trees into one valid BST, return the root of the resulting tree; otherwise, return null.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def merge_bsts(trees):
    if not trees:
        return None
    
    from collections import defaultdict
    
    leaf_to_tree = defaultdict(list)
    
    # Prepare the leaf to tree mapping
    for tree in trees:
        root = build_tree(tree)
        if root:
            add_leaves_to_map(root, leaf_to_tree)
    
    # Attempt to merge the trees
    root = None
    for tree in trees:
        root = build_tree(tree)
        if root and try_merge(root, leaf_to_tree):
            return root
    
    return None

def build_tree(nodes):
    if not nodes:
        return None
    root = TreeNode(nodes[0])
    # Assume nodes are given in level-order
    queue = [root]
    index = 1
    while queue and index < len(nodes):
        current = queue.pop(0)
        if index < len(nodes) and nodes[index] is not None:
            current.left = TreeNode(nodes[index])
            queue.append(current.left)
        index += 1
        if index < len(nodes) and nodes[index] is not None:
            current.right = TreeNode(nodes[index])
            queue.append(current.right)
        index += 1
    return root

def add_leaves_to_map(node, leaf_to_tree):
    if not node:
        return
    if not node.left and not node.right:
        leaf_to_tree[node.val].append(node)
    add_leaves_to_map(node.left, leaf_to_tree)
    add_leaves_to_map(node.right, leaf_to_tree)

def try_merge(node, leaf_to_tree):
    # Merge logic to ensure BST properties are maintained
    pass
← Back to All Questions