LeetCode 1932 - Merge BSTs to Create Single BST

This problem asks us to take multiple very small binary search trees (BSTs), each with at most three nodes, and attempt to merge them into a single valid BST. Each tree is represented by its root node in the array trees.

leetcodehardarrayhash-tabletreedepth-first-searchbinary-search-treebinary-tree

LeetCode Problem 1932

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to take multiple very small binary search trees (BSTs), each with at most three nodes, and attempt to merge them into a single valid BST. Each tree is represented by its root node in the array trees. The only operation allowed is to attach one tree to a leaf of another if the leaf's value matches the root of the second tree. After merging, we remove the attached tree from the list.

The input is an array of n root nodes, where 1 <= n <= 5 * 10^4, and each tree has 1 to 3 nodes. No two root values are the same. The output is either the root of the fully merged BST if possible, or null if no valid BST can be formed.

Important points include that each node in the trees may only have children but no grandchildren, so all trees are extremely small. Leaves are defined as nodes with no children. The BST property requires that all left descendants be strictly smaller than the node, and all right descendants be strictly larger.

Edge cases to consider include trees that cannot merge because no leaf matches another root, trees that merge but violate BST properties, and single-node trees which may simply become the leaf of another tree.

Approaches

Brute Force

A brute-force approach would attempt all possible sequences of merges. For each leaf in every tree, we would check if it matches the root of another tree and perform the merge recursively until either all trees are merged or no valid operations remain. While this guarantees correctness, it is computationally infeasible because the number of merge sequences grows factorially with the number of trees. This would be far too slow for n up to 50,000.

Optimal Approach

The key insight for an optimal solution is to use a hash map to quickly look up which trees could be merged based on leaf values. Instead of trying all sequences, we track which trees are leaves and which are roots. We then attempt to merge any tree whose root is a leaf of another tree. After merging, we ensure that the resulting tree still satisfies BST properties using range checks during a DFS traversal.

By precomputing root-to-tree mappings and leaf-to-parent relationships, we can merge trees in linear time relative to the total number of nodes. We also check that there is exactly one candidate root that is not a leaf in any other tree; this must be the final root if a valid BST exists.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Tries all merge sequences; infeasible for large n
Optimal O(n) O(n) Uses hash maps to track roots and leaves; merges in linear time

Algorithm Walkthrough

  1. Collect root and leaf information: Iterate over all trees. Map each root value to its tree, and track all leaf values along with their parent trees. Count how many trees contain each leaf.
  2. Identify the candidate final root: Only the root value that does not appear as any leaf can be the final root. If there is not exactly one such candidate, return null.
  3. Recursive merge: Starting from the candidate root, recursively attempt to merge any subtree whose root matches a leaf of the current tree. For each merge, remove the merged tree from the root map.
  4. BST validation: While merging, maintain a valid value range for each node. Use DFS to check that all nodes respect the BST property. If any violation occurs, return null.
  5. Final check: After merging, ensure that all trees have been consumed. If any tree remains unmerged, return null. Otherwise, return the fully merged root.

Why it works: Each merge only occurs when a leaf matches a root, ensuring that we never lose tree nodes. The BST validation guarantees the merged tree is valid. By selecting the unique root that is not a leaf in any tree, we ensure a single final tree emerges.

Python Solution

# 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
from typing import List, Optional

class Solution:
    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:
        if not trees:
            return None

        root_map = {tree.val: tree for tree in trees}
        leaves = set()
        count_leaves = {}

        # Collect all leaves and count occurrences
        for tree in trees:
            for child in (tree.left, tree.right):
                if child:
                    leaves.add(child.val)
                    count_leaves[child.val] = count_leaves.get(child.val, 0) + 1

        # Candidate root is a root that is not a leaf
        candidate_roots = [val for val in root_map if val not in leaves]
        if len(candidate_roots) != 1:
            return None
        root_val = candidate_roots[0]
        root = root_map[root_val]

        def merge(node: TreeNode, lower: int, upper: int) -> bool:
            if not node:
                return True
            if not (lower < node.val < upper):
                return False
            if node.val in root_map and node != root:
                sub = root_map.pop(node.val)
                node.left = sub.left
                node.right = sub.right
            return merge(node.left, lower, node.val) and merge(node.right, node.val, upper)

        if not merge(root, float('-inf'), float('inf')):
            return None
        return root if len(root_map) == 1 else None

Explanation: We build hash maps to quickly access trees by root value and count leaf occurrences. We select the root that is not anyone's leaf. The recursive merge function attaches subtrees when a leaf matches a root and validates the BST property using a range check. Finally, we ensure that all trees have been merged.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func canMerge(trees []*TreeNode) *TreeNode {
    rootMap := make(map[int]*TreeNode)
    leaves := make(map[int]int)

    for _, tree := range trees {
        rootMap[tree.Val] = tree
        if tree.Left != nil {
            leaves[tree.Left.Val]++
        }
        if tree.Right != nil {
            leaves[tree.Right.Val]++
        }
    }

    var candidateRoot *TreeNode
    for val, tree := range rootMap {
        if _, exists := leaves[val]; !exists {
            if candidateRoot != nil {
                return nil
            }
            candidateRoot = tree
        }
    }

    if candidateRoot == nil {
        return nil
    }

    var merge func(node *TreeNode, low, high int) bool
    merge = func(node *TreeNode, low, high int) bool {
        if node == nil {
            return true
        }
        if node.Val <= low || node.Val >= high {
            return false
        }
        if sub, exists := rootMap[node.Val]; exists && node != candidateRoot {
            node.Left = sub.Left
            node.Right = sub.Right
            delete(rootMap, node.Val)
        }
        return merge(node.Left, low, node.Val) && merge(node.Right, node.Val, high)
    }

    if !merge(candidateRoot, -1, 50001) {
        return nil
    }

    if len(rootMap) != 1 {
        return nil
    }
    return candidateRoot
}

Explanation: Go requires explicit nil checks and uses maps instead of Python dictionaries. The merge logic mirrors Python, ensuring range validation for BST and merging subtrees only when a leaf matches a root.

Worked Examples

Example 1: trees = [[2,1],[3,2,5],[5,4]]

Step Root Map Leaves Action
Initial {2,3,5} {1,2,4,5} Identify candidate root 3
Merge 2 into 3 {3,5} - Node 2 attached as left child
Merge 5 into 3 {3} - Node 5 attached as right child
Final {3} - Valid BST formed

Example 2: trees = [[5,3,8],[3,2,6]]

Step Action Result
Candidate root 5 Merge 3 into 5
Merge Violates BST (6 > 5 in left subtree) Return null

Example 3: trees = [[5,4],[3]]

Step Action Result
No leaf matches root - Return null

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each tree and node visited once; merge and validation in linear time
Space O(n) Hash maps for roots and leaves; recursion stack at most O(log n)

The complexity is linear because each tree has at most three nodes, so total nodes are O(n). Hash maps allow constant-time lookups for merges.