Merge BSTs to Create Single BST

Hard

#1763Time: 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.

Algorithms

Binary Search Depth-First Search

Data structures

Hash Table Tree Binary Tree

Prompt

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:

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]].

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]].

The resulting tree, shown above, is a valid BST, so return its root.

Example 2:

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]].

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:

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

Constraints:

n == trees.length
1 <= n <= 5 * 10⁴
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 * 10⁴.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

The core idea is to separate the problem into two main phases: construction and validation.

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.
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.
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.

1class Solution {2    public TreeNode canMerge(List<TreeNode> trees) {3        Map<Integer, TreeNode> subtrees = new HashMap<>();4        Set<Integer> childValues = new HashSet<>();5        int totalNodes = 0;6 7        for (TreeNode root : trees) {8            subtrees.put(root.val, root);9            totalNodes++;10            if (root.left != null) {11                childValues.add(root.left.val);12                totalNodes++;13            }14            if (root.right != null) {15                childValues.add(root.right.val);16                totalNodes++;17            }18        }19 20        TreeNode root = null;21        for (TreeNode tree : trees) {22            if (!childValues.contains(tree.val)) {23                if (root != null) return null; // More than one possible root24                root = tree;25            }26        }27 28        if (root == null) return null; // No root found29 30        subtrees.remove(root.val);31 32        // Iterative DFS for merging to avoid stack overflow33        Stack<TreeNode> stack = new Stack<>();34        stack.push(root);35 36        while (!stack.isEmpty()) {37            TreeNode node = stack.pop();38 39            // Check left child for merging40            if (node.left != null) {41                if (node.left.left == null && node.left.right == null && subtrees.containsKey(node.left.val)) {42                    TreeNode sub = subtrees.get(node.left.val);43                    node.left = sub;44                    subtrees.remove(sub.val);45                    stack.push(sub);46                } else {47                    stack.push(node.left);48                }49            }50 51            // Check right child for merging52            if (node.right != null) {53                if (node.right.left == null && node.right.right == null && subtrees.containsKey(node.right.val)) {54                    TreeNode sub = subtrees.get(node.right.val);55                    node.right = sub;56                    subtrees.remove(sub.val);57                    stack.push(sub);58                } else {59                    stack.push(node.right);60                }61            }62        }63 64        if (!subtrees.isEmpty()) return null; // Not all trees were merged65 66        int[] count = {0};67        if (isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE, count) && count[0] == totalNodes - (trees.size() - 1)) {68            return root;69        }70        return null;71    }72 73    private boolean isValidBST(TreeNode node, long min, long max, int[] count) {74        if (node == null) return true;75        if (node.val <= min || node.val >= max) return false;76        count[0]++;77        return isValidBST(node.left, min, node.val, count) && isValidBST(node.right, node.val, max, count);78    }79}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

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.
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.

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.

1class Solution {2    private int totalNodes = 0;3 4    public TreeNode canMerge(List<TreeNode> trees) {5        Map<Integer, TreeNode> subtrees = new HashMap<>();6        Set<Integer> childValues = new HashSet<>();7 8        for (TreeNode root : trees) {9            subtrees.put(root.val, root);10            totalNodes++;11            if (root.left != null) {12                childValues.add(root.left.val);13                totalNodes++;14            }15            if (root.right != null) {16                childValues.add(root.right.val);17                totalNodes++;18            }19        }20 21        TreeNode root = null;22        for (TreeNode tree : trees) {23            if (!childValues.contains(tree.val)) {24                if (root != null) return null; // More than one possible root25                root = tree;26            }27        }28 29        if (root == null) return null; // No root found30 31        subtrees.remove(root.val);32        int expectedNodes = totalNodes - (trees.size() - 1);33        int mergedNodeCount = dfs(root, Long.MIN_VALUE, Long.MAX_VALUE, subtrees);34 35        if (mergedNodeCount == expectedNodes && subtrees.isEmpty()) {36            return root;37        }38        return null;39    }40 41    private int dfs(TreeNode node, long min, long max, Map<Integer, TreeNode> subtrees) {42        if (node == null) return 0;43 44        if (node.val <= min || node.val >= max) return -1; // BST violation45 46        // If this node is a leaf that can be expanded47        if (node.left == null && node.right == null && subtrees.containsKey(node.val)) {48            TreeNode sub = subtrees.get(node.val);49            node.left = sub.left;50            node.right = sub.right;51            subtrees.remove(sub.val);52        }53 54        int leftCount = dfs(node.left, min, node.val, subtrees);55        if (leftCount == -1) return -1;56 57        int rightCount = dfs(node.right, node.val, max, subtrees);58        if (rightCount == -1) return -1;59 60        return 1 + leftCount + rightCount;61    }62}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1/** * 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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem