Merge Two BST
Difficulty: Medium
Asked in: Amazon, Microsoft, Google
Given two binary search trees with root nodes as
tree1
and
tree2
of size
n
and
m
, write a program to return an array of integers that contains all the elements of
tree1
and
tree2
in nondecreasing order.
Problem Note

The expected time complexity is O(
m+n
).
Example 1
Input: 3 4
/ \ / \
2 5 1 6
Output: [1, 2, 3, 4, 5, 6]
Explanation: The resultant binary tree contains all the elements of bst1 and bst2 in nondecreasing order.
Example 2
Input: 3 6
\ / \
4 2 10
Output:[2, 3, 4, 6, 10]
Explanation: Both bst1 and bst2 are combined to return the BST having all the elements of bst1 and bst2 in nondecreasing order.
Solutions
We will be discussing various solutions to this problem. Before that, you should be familiar with the properties of Binary Search Trees. Read Here.
 Naive Solution : Traverse on both the trees separately while storing them in respective arrays and then store each element in the 3rd array and return it after sorting.
 Sorted Merge: Inorder traversal of both trees will give two sorted arrays. Use the merge function of the merge sort to return the sorted array after merging them.
 Using Stacks: While inorder traversal, maintain two stacks that will store the current smallest element on the top for each tree and on that basis maintain the result array.
The TreeNode passed to the function will be:
class TreeNode{
TreeNode left
int val
TreeNode right
}
Give this problem a try on your own.
1. Naive Solution
The problem asks us to return the value of each node in a sorted array. So, the simplest way to solve this problem is to traverse the trees and store each of their node values in the respective two auxiliary arrays.
Create a
result
array and put all of the values from two auxiliary arrays inside it and then return the array after sorting it.
Solutions Steps

Create two arrays
arr1
andarr2.

Perform inorder traversal on both BST while adding node value in
arr1
andarr2
for each visit. 
Insert all the values of
arr1
andarr2
inresult
array. 
Sort the
result
array and return it.
Pseudo Code
int[] getAllElements(TreeNode root1,TreeNode root2) {
int[] arr1
int[] arr2
inorder(root1, arr1)
inorder(root2, arr2)
int[] result
for(i =0 to i < arr1.size()) {
result.push_back(arr1[i])
}
for(i =0 to i < arr2.size()) {
result.push_back(arr2[i])
}
result.sort()
return result
}
// inorder traversal
void inorder(TreeNode root, int[] arr) {
if(root) {
inorder(root.left)
arr.push_back(root.val)
inorder(root.right)
}
}
Complexity Analysis
Time Complexity : O(n log n), where n is the total number of nodes of tree1 and tree2.
Space Complexity : O(n)
Critical Ideas To Think
 Do we use any property of BST?
 Will this approach work if the tree is a binary tree instead of a binary search tree. If yes, Why?

Why do we sort the
result
array before returning it?  Can we do preorder or postorder traversal, instead of inorder traversal? Will the result array be affected by any traversal in this approach?
2. Sorted Merge
A very important property of BST is that, when we do inorder traversal on BST, we get a sorted array.
In this problem, we can use the above property as the problem demands us to return a sorted array. So, we can perform inorder traversal of both the BSTs and we will get two sorted arrays. Each of the arrays will contain all the node’s values of the respective BST.
Now, we have two sorted arrays, all we have to do is to merge them. If you have read about merge sort, then you would have known that during the “Combine” step, we merge two sorted arrays in linear time,
Read here
or
Read here
. Eventually, we will have the sorted
result
array and we could simply return it.
Solution Steps

Perform inorder traversal of
tree1
and store each node’s value inarr1.

Perform inorder traversal of
tree2
and store each node’s value inarr2.

Combine
arr1
andarr2
using merge function of merge sort to createresult
array. 
Return
result
array.
Pseudo Code
int[] getAllElements(TreeNode root1,TreeNode root2){
int[] arr1
int[] arr2
inorder(root1, arr1)
inorder(root2, arr2)
int[] result
merge(arr1, arr2, result)
return result
}
// utility Functions
void inorder(TreeNode root, int[] arr){
if(root){
inorder(root.left)
arr.push_back(root.val)
inorder(root.right)
}
}
void merge(int[] X, int[] Y, int[] result){
int i = 0, j = 0
while(i < X.size() and j < Y.size()){
if(X[i] > Y[j]){
result.push_back(Y[j])
j = j + 1
} else {
result.push_back(X[i])
i = i + 1
}
}
while(i < X.size()){
result.push_back(X[i])
i = i + 1
}
while(j < Y.size()){
result.push_back(Y[j])
j = j + 1
}
}
Complexity Analysis
Time Complexity
: O(n), where n is the total number of nodes of
tree1
and
tree2
.
Space Complexity : O(n) (Why?)
Critical Ideas To Think

What is the time complexity of inserting all nodes value in
arr
during inorder traversal?  How is the array sorted after the inorder traversal of BST?
 How did we merge both the arrays in linear time?
 Can you optimize the space complexity?
3. Using Stacks
Let’s think again about BST, we know that any element on the left side of the root is always going to be smaller than the root. And in this problem, to merging the two tree nodes, we can compare the two nodes of both the trees while adding into the result array simultaneously.
So, at any point in time, the comparisons that will be required to construct the
result
array will only be from those nodes which lie in the path from the root to the current node.
We can create two stacks for each tree and will maintain the stack as the smallest element on the top. Now, considering we have two stacks where the stack is sorted in ascending order from top to bottom, we can simply compare the top of both the stacks and put smaller ones in the result array, thereby popping up that element from the stack.
In this way, we could reduce memory usage as the maximum size of the stack will reach equal to the height of the tree. If the BST is heightbalanced BST, then this approach will significantly affect the space complexity.
Solution Steps

Create two stacks,
stack1
andstack2
 Iterate until tree1 is not NULL or tree2 is not NULL or stack1 is not empty or stack2 is not empty.
 For each iteration:

Push all the left nodes of
tree1
insidestack1

Push all the left nodes of
tree2
insidestack2

Compare the top of both the stacks, put the smaller one in the
result
while popping it out from the respective stack and move to its right child.

Return
result
Pseudo Code
int[] getAllElements(TreeNode root1,TreeNode root2) {
stack1 = Stack()
stack2 = Stack()
tree1 = root1
tree2 = root2
int[] result
while(tree1 or tree2 or stack1 or stack2) {
while (tree1) {
stack1.push(tree1)
tree1 = tree1.left
}
while (tree2) {
stack2.push(tree2)
tree2 = tree2.left
}
if (not stack2) or (stack1 and stack1.top().val <= stack2.top().val) {
tree1 = stack1.pop()
result.push_back(tree1.val)
tree1 = tree1.right
}
else {
tree2 = stack2.pop()
result.push_back(tree2.val)
tree2 = tree2.right
}
}
return result
}
Complexity Analysis
Time Complexity
: O(n), where n is the total number of nodes of
tree1
and
tree2
.
Space Complexity : O(n), If the BST is heightbalanced BST, then it’s O(log n)
Critical Ideas To Think
 In the above code, there is a nested while loop. So, how the time complexity is O(n)?
 How did we make sure that the stack at any point in time must be sorted from top to bottom?
 Why do we put all the left nodes inside the stacks at once and then compared the top of the stacks?

Dry the run the above code on
example1
andexample2
and verify how our approach works!
Comparison Of Solutions
Suggested Problems To Solve
 Merge K BST
 Merge two BST with constant extra space
 Kth largest element in BST
 Connect nodes at the same level of a binary tree
 Merge Two Sorted Arrays
Please comment down below if you have a better insight in the above approach.
Happy Coding, Enjoy Algorithms!