Merge BSTs to Create Single BST - Video Solutions
LeetCode 1932. Merge BSTs to Create Single BST
Merge BSTs to Create Single BST - Video Solution
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,561 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
iandjsuch that the value stored at one of the leaves oftrees[i]is equal to the root value oftrees[j]. - Replace the leaf node in
trees[i]withtrees[j]. - Remove
trees[j]fromtrees.
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.length1 <= 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
treeshave the same value. - All the trees in the input are valid BSTs.
1 <= TreeNode.val <= 5 * 104.
Approach Overview
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.
Complexity Analysis
| 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. |