Skip to main content
Talentd

Merge BSTs to Create Single BST - Solution & Explanation

HardHash TableBinary SearchTreeDepth-First Search10 min readAsked at: Amazon, Microsoft, Google
Practice this problem

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 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 * 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 trees have 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.

Approach 1: Union-Find Approach for Optimized Merging

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:

  • TreeNode class: Represents each node in the tree.
  • UnionFind class: Provides the union and find operation for managing sets of connected trees.
  • Solution class: Implements the canMerge function that checks if it's possible to merge BSTs into one. First, it initializes a union-find structure for the trees. Then, it attempts to connect the trees by checking if they share potential leaf connections (using a dictionary to speed up lookups). Finally, it verifies if all trees are connected to a single component, returning the result accordingly.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Top-Down Depth-First Search (DFS)

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:

  • Create maps: Prepare a map of tree roots and another for tracking visited nodes to avoid reprocessing.
  • DFS function: Performs recursive search to attempt merging node connections where possible, linking left and right children accordingly.
  • Final check: Ensures all nodes are visited and successfully merged, otherwise returns null as the merge is impossible.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n), the depth-first search processes nodes linearly.

Space Complexity: O(n), required for the map and recursive stack.

Try this approach in the editor →

Complexity Comparison

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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Union-Find Optimized MergingO(n)O(n)When you want explicit control over component merging and to prevent duplicate tree attachments.
Top-Down DFS Merge and ValidateO(n)O(n)Preferred interview approach when validating BST constraints during traversal.

Video Solution

LeetCode 1932. Merge BSTs to Create Single BST • Happy Coding • 4,561 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Merge BSTs to Create Single BST easy or hard?
LeetCode classifies this problem as Hard because it combines multiple concepts: BST validation, root detection, tree merging, and hash-based lookups. The challenge comes from ensuring all trees are used exactly once while preserving BST ordering constraints.
Merge BSTs to Create Single BST Python/Java solution
Typical implementations use a hash map that maps root values to tree nodes and a DFS function that enforces BST bounds. Python and Java solutions both follow the same pattern: identify the root, merge subtrees during traversal, and validate ordering. The runtime remains O(n) with O(n) auxiliary space.
How to solve Merge BSTs to Create Single BST in O(n)?
Store every root in a hash map and count how many times each value appears as a leaf. The root that never appears as a leaf becomes the final tree root. Run a DFS with min/max bounds and whenever a leaf matches another root value, merge that subtree and continue traversal. Each node is processed once, giving O(n) complexity.
What is the best approach for Merge BSTs to Create Single BST?
The most common approach is a top-down DFS that merges trees while validating BST bounds. First identify the global root using leaf frequency, then traverse while attaching trees when a leaf matches another root. This guarantees every node respects BST ordering and all trees are used exactly once. The overall complexity is O(n) time and O(n) space.
Is Merge BSTs to Create Single BST asked at Google/Amazon/Meta?
Hard tree and BST construction problems like this appear in interviews at companies such as Google, Amazon, and Meta. They test your ability to combine hash maps, tree traversal, and BST validation in one solution. Candidates are expected to reason about structure merging and correctness conditions.
What data structure is used in Merge BSTs to Create Single BST?
The core structures are hash tables for root lookup, binary search trees for maintaining sorted ordering, and depth-first search for traversal and validation. Some solutions also use union-find to track merged components and prevent duplicate merges.
What is the time complexity of Merge BSTs to Create Single BST?
The optimal solution runs in O(n) time where n is the total number of nodes across all trees. Each node is visited once during DFS and root lookups are constant time using a hash map. Space complexity is O(n) due to recursion stack and auxiliary maps.

Ready to solve this problem?

Practice Merge BSTs to Create Single BST with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters