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.
This approach uses a Union-Find (or Disjoint Set Union) data structure to help manage the merging process of BSTs. The idea is to treat each tree's root as a node in the union-find structure. We will iteratively attempt to merge trees by looking for leaf-root connections using a dictionary to map tree nodes. Whenever a connection is viable, we use union operations to efficiently manage the merging of trees.
Implementing Union-Find helps in efficiently finding the connected components and managing ids for quick union operations. Besides, this contributes to achieving optimal time complexity for this problem.
This code is structured into three main components:
Python
JavaScript
Time Complexity: O(n log n), where n is the number of trees. This is due to the efficient union and find operations with path compression.
Space Complexity: O(n), for union-find structures and dictionary.
This approach uses a top-down depth-first search (DFS) with backtracking to merge BSTs. Starting from each tree's root, attempt to recursively search and merge the trees using DFS, keeping track of visited nodes to avoid cycles and incorrect merges.
The key idea is to explore all possible merge paths and backtrack whenever a violation of the BST properties occurs. The algorithm handles edge cases and ensures all operations respect the properties of BSTs.
This C++ implementation uses a depth-first search approach:
Time Complexity: O(n), the depth-first search processes nodes linearly.
Space Complexity: O(n), required for the map and recursive stack.
| Approach | Complexity |
|---|---|
| Union-Find Approach for Optimized Merging | Time Complexity: O(n log n), where n is the number of trees. This is due to the efficient union and find operations with path compression. Space Complexity: O(n), for union-find structures and dictionary. |
| Top-Down Depth-First Search (DFS) | Time Complexity: O(n), the depth-first search processes nodes linearly. Space Complexity: O(n), required for the map and recursive stack. |
| 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. |
LeetCode 1932. Merge BSTs to Create Single BST • Happy Coding • 4,184 views views
Watch 5 more video solutions →Practice Merge BSTs to Create Single BST with our built-in code editor and test cases.
Practice on FleetCode