# Merge two Binary search Trees with constant extra space

In this article, I'll talk about Merging two Binary search trees with constant extra space.

**Problem**

You are given 2 Binary Search Trees. Your task is to print elements from both of these tress in sorted order.

**Examples**

**Input**

```
TREE 1:
6
/ \
2 9
TREE 2:
10
/ \
5 15
```

**Output**

`2 5 6 9 10 15`

**Input**

```
TREE 1:
5
/ \
4 7
/
1
TREE 2:
6
/
2
/
0
```

**Output**

`0 1 2 4 5 6 7`

**Solution**

We know that, left most element of BST i.e. first element in inorder traversal, is the smalles element of BST. Here we will use this property.

We'll fetch left most element of each BST and compare them, and smallest one and leave the other one as it is in its tree. The element which we just printed will be deleted from its tree.

After this deletion, we'll again get left most elemnt from both tree and print smaller one and delete it from its tree.

We'll keep repeating this process until we completely exhaust one tree.

After anyone of the trees is exhausted, we'll just traverse the other tree in inorder style and print all of its element.

*Time complexity* of this approach would be **O((X+Y)(h1+h2))**, given X and Y are the number of nodes of the each of the trees respectively and, h1 and h2 are the heights of trees respectively.

*Space complexity* would be **O(1)**

**Implementation**

Let's code this approach.

```
#include <bits/stdc++.h>
using namespace std;
// Node of Binary Search Tree
class Node {
public:
int data;
Node* left;
Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
// Inorder traversal of Tree
void inorder(Node* root)
{
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
// Required function to print data from both trees in sorted order
void PrintSorted(Node* root1, Node* root2)
{
// Condition to break recursion
if (!root1 && !root2)
return;
// If anyone of the first tree is exhausted
// print the inorder traversal of the second tree
if (!root1) {
inorder(root2);
return;
}
// If second tree is exhausted
// print the inoreder traversal of the first tree
if (!root2) {
inorder(root1);
return;
}
// A temporary to root of first tree
Node* temp1 = root1;
// store the parent of temporary pointer
Node* prev1 = NULL;
// Traverse through the first tree until you reach
// the leftmost element, which is the first element
// of the tree in the inorder traversal.
// This is the least element of the tree
while (temp1->left) {
prev1 = temp1;
temp1 = temp1->left;
}
// Another temporary pointer currently
// pointing to root of second tree
Node* temp2 = root2;
// Previous pointer to store the
// parent of second temporary pointer
Node* prev2 = NULL;
// Traverse through the second tree until you reach
// the leftmost element, which is the first element of
// the tree in inorder traversal.
// This is the least element of the tree.
while (temp2->left) {
prev2 = temp2;
temp2 = temp2->left;
}
// Compare the least current least
// elements of both the tree
if (temp1->data <= temp2->data) {
// If first tree's element is smaller print it
cout << temp1->data << " ";
// If the node has no parent, that
// means this node is the root
if (prev1 == NULL) {
// Simply make the right
// child of the root as new root
PrintSorted(root1->right, root2);
}
// If node has a parent
else {
// As this node is the leftmost node,
// it is certain that it will not have
// a let child so we simply assign this
// node's right pointer, which can be
// either null or not, to its parent's left
// pointer. This statement is
// just doing the task of deleting the node
prev1->left = temp1->right;
// recursively call the PrintSorted
// function with updated tree
PrintSorted(root1, root2);
}
}
else {
cout << temp2->data << " ";
// If the node has no parent, that
// means this node is the root
if (prev2 == NULL) {
// Simply make the right child
// of root as new root
PrintSorted(root1, root2->right);
}
// If node has a parent
else {
prev2->left = temp2->right;
// Recursively call the PrintSorted
// function with updated tree
PrintSorted(root1, root2);
}
}
}
// Main function
int main()
{
Node *root1 = NULL, *root2 = NULL;
root1 = new Node(3);
root1->left = new Node(1);
root1->right = new Node(5);
root2 = new Node(4);
root2->left = new Node(2);
root2->right = new Node(6);
// Print sorted nodes of both trees
PrintSorted(root1, root2);
return 0;
}
```

`1 2 3 4 5 6`