# Merge BSTs to Create Single BST
**Difficulty:** HARD
[External](https://leetcode.com/problems/merge-bsts-to-create-single-bst)
Canonical: https://scaleengineer.com/dsa/problems/merge-bsts-to-create-single-bst
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
---
## Problem
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_.

A BST (binary search tree) is a binary tree where each node satisfies the following property:

* Every node in the node's left subtree has a value **strictly less** than the node's value.
* Every node in the node's right subtree has a value **strictly greater** than the node's value.

A leaf is a node that has no children.

**Example 1:**

![](https://assets.glich.co/dsa/merge-bsts-to-create-single-bst/image0.png) 

**Input:** trees = [[2,1],[3,2,5],[5,4]]
**Output:** [3,2,5,1,null,4]
**Explanation:**
In the first operation, pick i=1 and j=0, and merge trees[0] into trees[1].
Delete trees[0], so trees = [[3,2,5,1],[5,4]].
![](https://assets.glich.co/dsa/merge-bsts-to-create-single-bst/image1.png)
In the second operation, pick i=0 and j=1, and merge trees[1] into trees[0].
Delete trees[1], so trees = [[3,2,5,1,null,4]].
![](https://assets.glich.co/dsa/merge-bsts-to-create-single-bst/image2.png)
The resulting tree, shown above, is a valid BST, so return its root.

**Example 2:**

![](https://assets.glich.co/dsa/merge-bsts-to-create-single-bst/image3.png) 

**Input:** trees = [[5,3,8],[3,2,6]]
**Output:** []
**Explanation:**
Pick i=0 and j=1 and merge trees[1] into trees[0].
Delete trees[1], so trees = [[5,3,8,2,6]].
![](https://assets.glich.co/dsa/merge-bsts-to-create-single-bst/image4.png)
The resulting tree is shown above. This is the only valid operation that can be performed, but the resulting tree is not a valid BST, so return null.

**Example 3:**

![](https://assets.glich.co/dsa/merge-bsts-to-create-single-bst/image5.png) 

**Input:** trees = [[5,4],[3]]
**Output:** []
**Explanation:** It is impossible to perform any operations.

**Constraints:**

* `n == trees.length`
* `1 <= n <= 5 * 104`
* The number of nodes in each tree is in the range `[1, 3]`.
* Each node in the input may have children but no grandchildren.
* No two roots of `trees` have the same value.
* All the trees in the input are **valid BSTs**.
* `1 <= TreeNode.val <= 5 * 104`.

# Approaches
## Map, Merge, then Validate
This approach first identifies the potential root of the final merged BST. It then constructs the full tree by iteratively attaching subtrees at leaf nodes with matching values. After the entire tree is built, it performs a separate validation pass to check if the resulting tree is a valid BST and contains all the nodes from the initial set of trees.
**Time:** O(N), where N is the total number of nodes across all trees. Preprocessing takes O(N). Merging involves traversing each node once, O(N). Validation also traverses each node once, O(N). The total complexity is dominated by these linear passes. · **Space:** O(N), where N is the total number of nodes across all trees. This is for the `subtrees` map, `childValues` set, and the stack for traversal, which in the worst case (a skewed tree) can hold O(N) nodes.
**Pros:** Conceptually straightforward by separating the construction and validation logic.; The logic for merging and validation is clear and distinct.
**Cons:** Builds the entire tree structure before validation, which can be inefficient if the structure is invalid early on.; Requires two separate traversals of the final tree structure: one for merging and one for validation.
### Explanation
The core idea is to separate the problem into two main phases: construction and validation.

1.  **Preprocessing and Root Finding**: We first iterate through all the given trees to gather information. We use a `Map<Integer, TreeNode>` to store each tree's root, keyed by its value, for quick lookups. We also use a `Set<Integer>` to store the values of all child nodes. The root of the final, merged BST cannot be a child of any other tree. Therefore, its value will not be in the set of child values. We iterate through the initial roots to find the unique one that satisfies this condition. If we find zero or more than one such root, a single BST cannot be formed.

2.  **Merging**: Once the root is identified, we start a traversal (an iterative DFS using a stack is a robust choice to prevent stack overflow) from this root. The goal is to build the complete tree. During the traversal, whenever we encounter a leaf node, we check our map of subtrees. If the leaf's value matches the root value of an available subtree, we perform the merge operation: the leaf node is replaced by the entire subtree. We then remove the merged subtree from our map and continue the traversal, now including the nodes of the newly attached subtree.

3.  **Validation**: After the merging process, we check if all subtrees were successfully merged by seeing if our map of subtrees is empty. If it is, we proceed to validate the constructed tree. A helper function recursively checks two properties: that the BST property (left child < node < right child) holds for all nodes, and that the total node count is correct. The final node count should be the sum of nodes in all initial trees minus `(n-1)`, as each of the `n-1` merge operations effectively removes one leaf node. If both conditions are met, the tree is valid.

```java
class Solution {
    public TreeNode canMerge(List<TreeNode> trees) {
        Map<Integer, TreeNode> subtrees = new HashMap<>();
        Set<Integer> childValues = new HashSet<>();
        int totalNodes = 0;

        for (TreeNode root : trees) {
            subtrees.put(root.val, root);
            totalNodes++;
            if (root.left != null) {
                childValues.add(root.left.val);
                totalNodes++;
            }
            if (root.right != null) {
                childValues.add(root.right.val);
                totalNodes++;
            }
        }

        TreeNode root = null;
        for (TreeNode tree : trees) {
            if (!childValues.contains(tree.val)) {
                if (root != null) return null; // More than one possible root
                root = tree;
            }
        }

        if (root == null) return null; // No root found

        subtrees.remove(root.val);

        // Iterative DFS for merging to avoid stack overflow
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            // Check left child for merging
            if (node.left != null) {
                if (node.left.left == null && node.left.right == null && subtrees.containsKey(node.left.val)) {
                    TreeNode sub = subtrees.get(node.left.val);
                    node.left = sub;
                    subtrees.remove(sub.val);
                    stack.push(sub);
                } else {
                    stack.push(node.left);
                }
            }

            // Check right child for merging
            if (node.right != null) {
                if (node.right.left == null && node.right.right == null && subtrees.containsKey(node.right.val)) {
                    TreeNode sub = subtrees.get(node.right.val);
                    node.right = sub;
                    subtrees.remove(sub.val);
                    stack.push(sub);
                } else {
                    stack.push(node.right);
                }
            }
        }

        if (!subtrees.isEmpty()) return null; // Not all trees were merged

        int[] count = {0};
        if (isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE, count) && count[0] == totalNodes - (trees.size() - 1)) {
            return root;
        }
        return null;
    }

    private boolean isValidBST(TreeNode node, long min, long max, int[] count) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        count[0]++;
        return isValidBST(node.left, min, node.val, count) && isValidBST(node.right, node.val, max, count);
    }
}
```
### Algorithm
- Create a map `valToNode` from root values to `TreeNode` objects for all trees.
- Create a set `childValues` containing all values that appear as children in any tree.
- Determine the root of the final BST. It must be the root of a tree whose value is not in `childValues`. If there isn't exactly one such root, it's impossible to form a single BST.
- Create a copy of the `valToNode` map, let's call it `subtrees`, and remove the final root from it. `subtrees` now holds all the trees that need to be merged.
- Perform a traversal (like DFS or BFS) starting from the final root. When a leaf node is encountered, check if its value corresponds to a root in the `subtrees` map.
- If it does, replace the leaf node with the corresponding subtree from the map and remove that subtree from the map. Continue the traversal into the newly attached subtree.
- After the traversal, check if the `subtrees` map is empty. If not, it means some trees were not merged, indicating disconnected components, so the result is invalid.
- If all subtrees are merged, perform a full validation on the resulting tree. This involves two checks:
  1. The tree must be a valid BST. This can be checked with a recursive traversal that verifies the BST property at each node (`min < node.val < max`).
  2. The total number of nodes in the final tree must match the expected count. The expected count is the total number of nodes in all initial trees minus `(n-1)` (since `n-1` leaves are replaced).

## Single Pass Merge and Validate
This optimized approach combines the merging and validation steps into a single, efficient traversal. As it builds the tree by attaching subtrees, it simultaneously validates the BST property. This allows the process to fail fast, immediately stopping and returning `null` if an invalid merge is attempted, without building the rest of the potentially large, incorrect tree.
**Time:** O(N), where N is the total number of nodes. The algorithm performs one pass for preprocessing and one combined pass for merging and validation. Each node is visited a constant number of times. · **Space:** O(N), where N is the total number of nodes. This space is used for the `subtrees` map, `childValues` set, and the recursion stack. The recursion depth can be up to O(N) in the worst case of a skewed tree.
**Pros:** More efficient in practice for invalid inputs due to early termination (fail-fast).; Combines merging and validation into a single traversal, reducing overhead.
**Cons:** The recursive implementation can lead to a `StackOverflowError` for very deep trees, although this is a risk in the validation step of the previous approach as well.; The combined logic within a single function can be slightly more complex to reason about and implement correctly.
### Explanation
This approach improves upon the first one by integrating the validation check into the merging process. This avoids constructing an invalid tree completely, only to discard it later.

1.  **Preprocessing and Root Finding**: This part is identical to the first approach. We build a map of subtrees, identify all child node values, and find the single root of the final tree.

2.  **Single-Pass Merge and Validate**: We use a single recursive function to handle both merging and validation. This function, let's call it `dfs`, takes the current node, the valid range `(min, max)` for its value, and the map of available subtrees. 

As `dfs` traverses the tree, it first checks if the current node's value is within the `(min, max)` bounds. If not, the BST property is violated, and it immediately signals an error. Then, it looks at its children. If a child is a leaf node whose value matches a root in our subtree map, it performs the merge by replacing the leaf with the subtree. Crucially, it then makes a recursive call on this newly attached subtree, passing down the updated `(min, max)` constraints. For example, for a new subtree attached as a left child of `node`, all its values must be less than `node.val`. If at any point a recursive call signals an error, it's propagated up, halting the process.

The function returns the number of nodes in the validly formed subtree. 

3.  **Final Check**: After the initial call on the root completes, we check two conditions: did the process complete without error, and were all subtrees used? This is verified by checking if the returned node count equals the expected total (`totalNodes - (n-1)`) and if the subtree map is now empty. If both are true, we have a valid merged BST.

```java
class Solution {
    private int totalNodes = 0;

    public TreeNode canMerge(List<TreeNode> trees) {
        Map<Integer, TreeNode> subtrees = new HashMap<>();
        Set<Integer> childValues = new HashSet<>();

        for (TreeNode root : trees) {
            subtrees.put(root.val, root);
            totalNodes++;
            if (root.left != null) {
                childValues.add(root.left.val);
                totalNodes++;
            }
            if (root.right != null) {
                childValues.add(root.right.val);
                totalNodes++;
            }
        }

        TreeNode root = null;
        for (TreeNode tree : trees) {
            if (!childValues.contains(tree.val)) {
                if (root != null) return null; // More than one possible root
                root = tree;
            }
        }

        if (root == null) return null; // No root found

        subtrees.remove(root.val);
        int expectedNodes = totalNodes - (trees.size() - 1);
        int mergedNodeCount = dfs(root, Long.MIN_VALUE, Long.MAX_VALUE, subtrees);

        if (mergedNodeCount == expectedNodes && subtrees.isEmpty()) {
            return root;
        }
        return null;
    }

    private int dfs(TreeNode node, long min, long max, Map<Integer, TreeNode> subtrees) {
        if (node == null) return 0;

        if (node.val <= min || node.val >= max) return -1; // BST violation

        // If this node is a leaf that can be expanded
        if (node.left == null && node.right == null && subtrees.containsKey(node.val)) {
            TreeNode sub = subtrees.get(node.val);
            node.left = sub.left;
            node.right = sub.right;
            subtrees.remove(sub.val);
        }

        int leftCount = dfs(node.left, min, node.val, subtrees);
        if (leftCount == -1) return -1;

        int rightCount = dfs(node.right, node.val, max, subtrees);
        if (rightCount == -1) return -1;

        return 1 + leftCount + rightCount;
    }
}
```
### Algorithm
- Perform the same preprocessing as the previous approach: build the `valToNode` map, the `childValues` set, and find the unique final root.
- Instead of separate merge and validate steps, combine them into a single recursive traversal.
- Define a recursive helper function, say `mergeAndValidate(node, min, max, subtrees)`, that attempts to build the tree while simultaneously checking for BST validity.
- This function will return the number of nodes in the validly constructed subtree, or an error code (e.g., -1) if any invalidity is found.
- Inside the function, for the current `node`:
  1. Check if `node.val` is within the valid range `(min, max)`. If not, return -1.
  2. Check if the left child is a leaf that can be replaced. If so, replace it with the corresponding subtree from the `subtrees` map.
  3. Recursively call `mergeAndValidate` for the left child with an updated `max` bound (`node.val`). If the recursive call returns -1, propagate the error.
  4. Do the same for the right child, updating the `min` bound (`node.val`).
  5. If both children are valid, return `1 + left_subtree_size + right_subtree_size`.
- Call this function on the root. After the call, check if the returned node count is correct (`totalNodes - (n-1)`) and if all subtrees have been used (`subtrees` map is empty). If both are true, the merge was successful.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public 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 { public TreeNode canMerge ( List < TreeNode > trees ) { Map < Integer , TreeNode > valRootMap = new HashMap < Integer , TreeNode >(); Map < TreeNode , int []> minMaxMap = new HashMap < TreeNode , int []>(); Map < TreeNode , int []> legalRangeMap = new HashMap < TreeNode , int []>(); for ( TreeNode root : trees ) { valRootMap . put ( root . val , root ); getMinMax ( minMaxMap , root ); getLegalRange ( legalRangeMap , root , Integer . MIN_VALUE , Integer . MAX_VALUE ); } Map < Integer , Integer > leavesCountMap = new HashMap < Integer , Integer >(); for ( TreeNode tree : trees ) visitLeaves ( leavesCountMap , tree , true ); for ( Map . Entry < Integer , Integer > entry : leavesCountMap . entrySet ()) { if ( entry . getValue () > 1 ) return null ; } Set < TreeNode > set = new HashSet < TreeNode >( trees ); for ( TreeNode root : trees ) { if ( isLeaf ( root )) continue ; TreeNode parent = getLeafParent ( root ); TreeNode left = parent . left , right = parent . right ; if ( left != null && valRootMap . containsKey ( left . val )) { int [] legalRange = legalRangeMap . get ( left ); TreeNode prevRoot = valRootMap . get ( left . val ); int [] minMax = minMaxMap . get ( prevRoot ); if ( minMax [ 0 ] < legalRange [ 0 ] || minMax [ 1 ] > legalRange [ 1 ]) return null ; parent . left = prevRoot ; legalRangeMap . put ( prevRoot , legalRange ); int [] parentMinMax = minMaxMap . get ( parent ); int [] newMinMax = { minMax [ 0 ], parentMinMax [ 1 ]}; minMaxMap . put ( prevRoot , newMinMax ); set . remove ( prevRoot ); } if ( right != null && valRootMap . containsKey ( right . val )) { int [] legalRange = legalRangeMap . get ( right ); TreeNode prevRoot = valRootMap . get ( right . val ); int [] minMax = minMaxMap . get ( prevRoot ); if ( minMax [ 0 ] < legalRange [ 0 ] || minMax [ 1 ] > legalRange [ 1 ]) return null ; parent . right = prevRoot ; legalRangeMap . put ( prevRoot , legalRange ); int [] parentMinMax = minMaxMap . get ( parent ); int [] newMinMax = { parentMinMax [ 0 ], minMax [ 1 ]}; minMaxMap . put ( prevRoot , newMinMax ); set . remove ( prevRoot ); } } if ( set . size () != 1 ) return null ; List < TreeNode > remain = new ArrayList < TreeNode >( set ); TreeNode root = remain . get ( 0 ); if ( isValidBST ( root )) return root ; return null ; } public void getMinMax ( Map < TreeNode , int []> minMaxMap , TreeNode root ) { TreeNode minNode = root , maxNode = root ; while ( minNode . left != null ) minNode = minNode . left ; while ( maxNode . right != null ) maxNode = maxNode . right ; minMaxMap . put ( root , new int []{ minNode . val , maxNode . val }); } public void getLegalRange ( Map < TreeNode , int []> legalRangeMap , TreeNode node , int min , int max ) { if ( node == null ) return ; legalRangeMap . put ( node , new int []{ min , max }); getLegalRange ( legalRangeMap , node . left , min , node . val - 1 ); getLegalRange ( legalRangeMap , node . right , node . val + 1 , max ); } public void visitLeaves ( Map < Integer , Integer > leavesCountMap , TreeNode node , boolean isRoot ) { if ( isLeaf ( node )) { if (! isRoot ) leavesCountMap . put ( node . val , leavesCountMap . getOrDefault ( node . val , 0 ) + 1 ); } else { if ( node . left != null ) visitLeaves ( leavesCountMap , node . left , false ); if ( node . right != null ) visitLeaves ( leavesCountMap , node . right , false ); } } public boolean isLeaf ( TreeNode node ) { return node != null && node . left == null && node . right == null ; } public TreeNode getLeafParent ( TreeNode root ) { if ( root . left != null && root . right != null ) return root ; if ( root . left != null ) { if ( isLeaf ( root . left )) return root ; else return root . left ; } else { if ( isLeaf ( root . right )) return root ; else return root . right ; } } public boolean isValidBST ( TreeNode root ) { if ( root == null ) return true ; TreeNode prev = null ; boolean flag = false ; Deque < TreeNode > stack = new LinkedList < TreeNode >(); TreeNode node = root ; while (! stack . isEmpty () || node != null ) { while ( node != null ) { stack . push ( node ); node = node . left ; } TreeNode curr = stack . pop (); if ( prev != null ) { if ( prev . val >= curr . val ) return false ; } prev = curr ; node = curr . right ; } return true ; } }
```