Watch 6 video solutions for Merge BSTs to Create Single BST, a hard level problem involving Hash Table, Binary Search, Tree. This walkthrough by Happy Coding has 4,184 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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].trees[i] with trees[j].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:
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.length1 <= n <= 5 * 104[1, 3].trees have the same value.1 <= TreeNode.val <= 5 * 104.Problem Overview: You are given several small binary search trees. Each tree has at most two children and may share leaf values with roots of other trees. The task is to merge these trees into a single valid BST by attaching trees at matching leaf nodes. If a valid BST cannot be formed using all trees exactly once, return null.
Approach 1: Union-Find Approach for Optimized Merging (O(n) time, O(n) space)
This strategy treats each tree root as a component and merges them when a leaf matches another root value. A hash table maps root values to their tree nodes for constant-time lookup. When visiting a leaf, check if another tree exists with that value as its root, then attach it and union the components to prevent duplicate merges. After all merges, run a BST validation using bounds to ensure every node respects the ordering rules. The union-find structure guarantees each tree is merged at most once, keeping operations near linear time.
Approach 2: Top-Down Depth-First Search (DFS) (O(n) time, O(n) space)
This approach identifies the global root first. Count the frequency of all node values; the true root is the only root value that never appears as a leaf. Store all trees in a map for quick access, then perform a top-down DFS while enforcing BST bounds (min < node.val < max). Whenever the traversal reaches a leaf whose value equals another root, merge that tree in place and continue DFS. The recursion ensures both structural merging and BST validation happen simultaneously. If any value violates BST constraints or not all trees are used, the merge fails.
Recommended for interviews: The DFS merge approach is typically what interviewers expect. It demonstrates understanding of binary search tree invariants, root detection, and recursive validation. The union-find version is slightly more system-oriented and useful when discussing component merging and preventing duplicate attachments. Showing the DFS idea first and then explaining how union-find can enforce merge correctness signals strong problem-solving depth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find Optimized Merging | O(n) | O(n) | When you want explicit control over component merging and to prevent duplicate tree attachments. |
| Top-Down DFS Merge and Validate | O(n) | O(n) | Preferred interview approach when validating BST constraints during traversal. |