## Merge Two BST

Difficulty: Medium

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 non-decreasing 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 non-decreasing 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 non-decreasing 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.

1. 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.
2. 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.
3. 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 ``` and ``` arr2. ```
• Perform inorder traversal on both BST while adding node value in ``` arr1 ``` and ``` arr2 ``` for each visit.
• Insert all the values of ``` arr1 ``` and ``` arr2 ``` in ``` result ``` 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 in-order 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 in-order 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 in-order 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 in ``` arr1. ```
• Perform inorder traversal of ``` tree2 ``` and store each node’s value in ``` arr2. ```
• Combine ``` arr1 ``` and ``` arr2 ``` using merge function of merge sort to create ``` result ``` 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 in-order traversal?
• How is the array sorted after the in-order 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 height-balanced BST, then this approach will significantly affect the space complexity.

Solution Steps

• Create two stacks, ``` stack1 ``` and ``` stack2 ```
• Iterate until tree1 is not NULL or tree2 is not NULL or stack1 is not empty or stack2 is not empty.
• For each iteration:
1. Push all the left nodes of ``` tree1 ``` inside ``` stack1 ```
2. Push all the left nodes of ``` tree2 ``` inside ``` stack2 ```
3. 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 height-balanced 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 ``` and ``` example2 ``` and verify how our approach works!

#### 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!