CareerCup

That would require O(n) space. Can this be done in constant space

It's straight forward if two BSTs are converted to LL first. Sorted LL merging is done in-place.

Do inorder traversal for one tree and for each element traversed insert the same in the other one...

I think you can treat this as the delete node algorithm of the BST where the node deleted is the root node.

Will this algorithm work? Assume the two trees are T1 with root1 and T2 with root 2. Assume we are going to merge(insert) T2 into T1

Node Insert(root1,root2)
{
if(root2==null)
return ;

find_place_to_insert_in_T1(root2);
if(root2 is left child of parent)
{
Node temp=insert(root1,root2->right);
if(temp!=root2)
root2->right=Null;
}
else
Node temp=insert(root1,root2->right);
if(temp!=root2)
root2->right=Null;

Will this algorithm work? Assume the two trees are T1 with root1 and T2 with root 2. Assume we are going to merge(insert) T2 into T1. Sorry code was incomplete last time.

Node Insert(root1,root2)
{
if(root2==null)
return ;

find_place_to_insert_in_T1(root2);
if(root2 is left child of parent)
{
Node temp=insert(root1,root2->right);
if(temp!=root2)
root2->right=Null;
}
else
{
Node temp=insert(root1,root2->left);
if(temp!=root2)
root2->left=Null;
}
return parent of root2
}

Basically the code is trying to find a place to insert a node with its children into another tree. If the node is inserted as a left child, then all its left children preserve the BST property but the right children may violate it so inserting the right children again from the top. Vice versa if node is inserted as right child. The check is to reset the pointer. In case the right child is not assigned to the same place as before, we need to reset the pointer to null. An optimisation is to pass the current parent into the recursion. So in case the node is inserted into the same place, then one need not call the recursion for its children since it preserves the BST property inherently.

Lets say the two trees are
V1 V2
/ \ / \
L1 R1 L2 R2
where V1,V2 are the values of roots and L1,L2,R1,R2 are the left and right sub trees.

1)Check which of V1,V2 is bigger and make that the root of our final answer(lets say V2>V1)
2)Then we make it root of the final merged tree.
3)Now we can surely say that( V1 )and L2 will be on left of V2
( / )
( L1 )
4)therefore let X=Merge(V1_L1_tree , L2)
5)Now nodes in R1, can lie either to the left or right of V2
6)therefore let Y=Merge(V2_R2_tree , R1)
7)After this, we can safely merge the left subtree of Y with X and make the head of this result as the left child of root of Y.
8)Not we need to specifically see the fact that we said 3) with respect to V2 but when we were making Y, it might have happened that V2 was replaced from the head of Y(and may be 3) would not hold then) but that will happen only in case R1->value > V2->value (as the bigger value is made root as in 1) ) and still 3) will hold

The solution is from 1-7. 8 is just proof
Please mention if anybody finds any mistake.

* 3)Now we can surely say that( V1_L1_tree )and L2 will be on left of V2

Node * merge(Node * r, Node * s) {
    if (!r)
        return s;
    if (!s)
        return r;
    if (r->d <= s->d) {
        Node * rright = r->right;
        r->right = NULL;
        Node * l = merge(r, s->left);
        s->left = l;
        return merge(rright, s);
    }
    else {return merge(s, r);}
}

This can be done in linear time and constant extra space
There are three steps:
Suppose number of nodes in first BST is n and in Second BST is m.

Step 1:: Convert both the BSTs to DLL             this takes O(n) + O(m) time and O(1) space
Step 2:: merge the two DLLs in place              this takes O(n+m) time and O(1) space
Step 3:: Convert the merged DLL to BST          this takes O(n+m) time and O(1) space

Step 1 and 2 are very easy.
Step 3 is the trickiest one , refer to this post :: geeksforgeeks.org/archives/18611

Just delete elements from one tree, and insert them into the other.

inorder operation for both Trees.
Merge two sorted array.
Create a BST by the merged array.