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.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:
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:
Java
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. |
L50. Binary Search Tree Iterator | BST | O(H) Space • take U forward • 174,563 views views
Watch 9 more video solutions →Practice Merge BSTs to Create Single BST with our built-in code editor and test cases.
Practice on FleetCode