DSA Tracker

Hard

Merge Two BSTs

A hard BST problem included in Love Babbar 450. Below: the roles whose interviews prioritise this topic, and how to practise it.

Topic
BST
Sheets
1
Core for
2 roles
Platform
GeeksforGeeks
Practice in the compilerWatch this solved step by step

The problem

Given two binary search trees, merge all elements from both trees into a single BST containing all values from both trees. Return the root of the merged BST.

Example 1

Input
root1=[2,1,4], root2=[1,0,3]
Output
[2,1,3,0,null,null,4]
Why
Merged values are {0,1,1,2,3,4}. A valid BST can be formed with root 2, left subtree 1,0 and right subtree 3,4.

Example 2

Input
root1=[2], root2=[1]
Output
[2,1]
Why
Merged values {1,2}. A valid BST has root 2 with left child 1.

Example 3

Input
root1=[1], root2=[3]
Output
[2,1,3]
Why
Merged values {1,3}. A balanced BST has root 2 with left 1 and right 3.

Constraints

  • The number of nodes in each tree is in the range [0, 5000].
  • -105 <= Node.val <= 105

How to think about it

Updated 2026-09-09

Merging two BSTs directly by repeated insertion takes quadratic time on skewed trees. Flattening each BST into an inorder sequence yields two already-sorted streams. Merging two sorted arrays is a standard linear two-pointer merge, and converting that combined sorted array into a balanced BST recursively takes linear time.

Approaches, worst first

  1. Insert elements one by one

    time O(m * h1) · space O(h1)

    Traverse tree2 and insert each node into tree1 using standard BST insertion. Simple, but if tree1 becomes unbalanced or tree2 is already sorted, insertion degrades to quadratic time in the worst case.

  2. Dump, merge, rebuild balanced

    time O(m + n) · space O(m + n)

    Extract inorder lists from both trees (size m and n), merge the two sorted lists using two pointers into a combined array of size m + n, and recursively pick the middle element as root to build a height-balanced BST.

  3. Iterative DLL conversion and mergeWrite this one

    time O(m + n) · space O(h1 + h2)

    Flatten both BSTs in-place into sorted doubly linked lists, merge the two linked lists, and reconstruct a balanced BST bottom-up from the linked list. Achieves minimal overhead without array allocations.

Where people lose marks · 2
  • Handling empty trees: either `root1` or `root2` may be empty (0 nodes), in which case the function must return the non-empty tree directly without null pointer exceptions.
  • Choosing middle element index: using `(left + right) / 2` with proper integer division avoids infinite recursion during balanced tree reconstruction.

The theory behind it

BST — the ground this problem stands on. All BST problems

What BST is

A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.

When to reach for it

Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.

How the pattern works

Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.

What each operation costs

OperationTime
search, insert, or delete on balanced treeO(log n)
search, insert, or delete on degenerate line treeO(n)
in-order traversal visiting all nodes in sorted orderO(n)
What usually goes wrong with BST
  • Validating a tree by checking only immediate children against the parent, missing violations where a node deep in the left subtree is larger than an ancestor higher up.
  • Allowing duplicate values on the wrong side when the problem specification requires strictly smaller values on the left and strictly greater on the right.
  • Deleting a node with two children by removing it directly instead of replacing its value with its in-order predecessor or successor and deleting that leaf instead.

Which roles need this problem

BST is a core topic for these 2 roles — if you're targeting one of them, this problem is early in your path, not optional.

SDE / Backend EngineerDatabase Engineer

Secondary for 6 more roles, including Full-Stack Developer, Android Developer, iOS Developer.

Track this in your role's order

Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.

Start free

More BST problems

Problem set and role mapping as of .