Binary Search TreesProblem 11 of 22Important
Merge two BST [V.V.V.IMP]
Problem Statement
Given two Binary Search Trees, merge them into a single balanced BST.
Example:
BST 1: BST 2: Merged Balanced BST:
3 5 4
/ \ / \ / \
1 4 2 6 2 6
/ \ / \
1 3 5 7
Inorder of BST1: [1, 3, 4]
Inorder of BST2: [2, 5, 6]
Merged Inorder: [1, 2, 3, 4, 5, 6]
Approach 1: Brute Force (Combine and Sort)
Intuition
Extract all elements from both BSTs, combine them, sort, and build a balanced BST.
Algorithm
- Extract all elements from BST1
- Extract all elements from BST2
- Combine both arrays
- Sort the combined array
- Build balanced BST from sorted array
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void extractValues(TreeNode root, List<Integer> values) {
if (root == null) return;
extractValues(root.left, values);
values.add(root.val);
extractValues(root.right, values);
}
private TreeNode buildBalancedBST(List<Integer> values, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(values.get(mid));
root.left = buildBalancedBST(values, left, mid - 1);
root.right = buildBalancedBST(values, mid + 1, right);
return root;
}
public TreeNode mergeBSTsBruteForce(TreeNode root1, TreeNode root2) {
List<Integer> values = new ArrayList<>();
extractValues(root1, values);
extractValues(root2, values);
Collections.sort(values);
return buildBalancedBST(values, 0, values.size() - 1);
}
}Complexity Analysis
- Time Complexity: O((m+n) log(m+n)) - Sorting dominates
- Space Complexity: O(m+n) - Storing all elements
Approach 2: Optimal (Merge Sorted Arrays)
Intuition
Since inorder of BST is sorted, we get two sorted arrays. Instead of sorting again, merge them like merge sort's merge step.
Algorithm
- Get inorder traversal of BST1 (sorted array 1)
- Get inorder traversal of BST2 (sorted array 2)
- Merge two sorted arrays in O(m+n)
- Build balanced BST from merged array
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> arr) {
if (root == null) return;
inorder(root.left, arr);
arr.add(root.val);
inorder(root.right, arr);
}
private List<Integer> mergeSortedArrays(List<Integer> arr1, List<Integer> arr2) {
List<Integer> merged = new ArrayList<>();
int i = 0, j = 0;
while (i < arr1.size() && j < arr2.size()) {
if (arr1.get(i) <= arr2.get(j)) {
merged.add(arr1.get(i++));
} else {
merged.add(arr2.get(j++));
}
}
while (i < arr1.size()) merged.add(arr1.get(i++));
while (j < arr2.size()) merged.add(arr2.get(j++));
return merged;
}
private TreeNode buildBalancedBST(List<Integer> arr, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(arr.get(mid));
root.left = buildBalancedBST(arr, left, mid - 1);
root.right = buildBalancedBST(arr, mid + 1, right);
return root;
}
public TreeNode mergeBSTs(TreeNode root1, TreeNode root2) {
// Step 1: Get inorder traversals
List<Integer> arr1 = new ArrayList<>();
List<Integer> arr2 = new ArrayList<>();
inorder(root1, arr1);
inorder(root2, arr2);
// Step 2: Merge sorted arrays
List<Integer> merged = mergeSortedArrays(arr1, arr2);
// Step 3: Build balanced BST
return buildBalancedBST(merged, 0, merged.size() - 1);
}
}Complexity Analysis
- Time Complexity: O(m+n) - Linear merge and build
- Space Complexity: O(m+n) - Storing arrays and result
Approach 3: Space Optimized (Convert to DLL, Merge, Convert Back)
Intuition
Convert both BSTs to sorted doubly linked lists, merge the lists, then convert back to balanced BST. This can be done with O(h1 + h2) extra space for recursion.
Algorithm
- Convert BST1 to sorted DLL
- Convert BST2 to sorted DLL
- Merge two sorted DLLs
- Convert merged DLL to balanced BST
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode prev, head;
private void bstToDLL(TreeNode root) {
if (root == null) return;
bstToDLL(root.left);
if (prev == null) {
head = root;
} else {
prev.right = root;
root.left = prev;
}
prev = root;
bstToDLL(root.right);
}
private TreeNode mergeDLLs(TreeNode head1, TreeNode head2) {
if (head1 == null) return head2;
if (head2 == null) return head1;
TreeNode dummy = new TreeNode(0);
TreeNode tail = dummy;
while (head1 != null && head2 != null) {
if (head1.val <= head2.val) {
tail.right = head1;
head1.left = tail;
head1 = head1.right;
} else {
tail.right = head2;
head2.left = tail;
head2 = head2.right;
}
tail = tail.right;
}
if (head1 != null) {
tail.right = head1;
head1.left = tail;
}
if (head2 != null) {
tail.right = head2;
head2.left = tail;
}
TreeNode result = dummy.right;
if (result != null) result.left = null;
return result;
}
private int countNodes(TreeNode head) {
int count = 0;
while (head != null) {
count++;
head = head.right;
}
return count;
}
private TreeNode dllToBST(int n) {
if (n <= 0 || head == null) return null;
TreeNode left = dllToBST(n / 2);
TreeNode root = head;
root.left = left;
head = head.right;
root.right = dllToBST(n - n / 2 - 1);
return root;
}
public TreeNode mergeBSTsOptimized(TreeNode root1, TreeNode root2) {
prev = null; head = null;
bstToDLL(root1);
TreeNode head1 = head;
prev = null; head = null;
bstToDLL(root2);
TreeNode head2 = head;
TreeNode mergedHead = mergeDLLs(head1, head2);
int n = countNodes(mergedHead);
head = mergedHead;
return dllToBST(n);
}
}Complexity Analysis
- Time Complexity: O(m+n) - All operations are linear
- Space Complexity: O(h1 + h2) for recursion, O(1) extra (in-place DLL)
Key Takeaways
- Leverage sorted property: Inorder of BST is sorted - use merge, not sort
- Three approaches: Sort (O(n log n)), Merge arrays (O(n)), DLL method (O(n), less space)
- DLL technique: Useful when space is constrained
- Balanced output: Always build balanced BST for optimal future operations
- Very important problem - frequently asked in interviews
- Similar to merge step in merge sort
- The merged BST has O(log(m+n)) height for balanced operations