There are other approaches possible to merging the Binary Search Tree

1) Add the elements of one tree to the other one at a time by moving the root until there are no more nodes in the tree 

2) Transform one of the trees into inorder and insert the items into the other tree. 

3) Jointly traverse both trees to find the minimum in either tree, delete it and add to a new BST 

  

Deleting a node from a tree 

Node TreeDelete(ref node root, node z) 

{ 

If (z==null) return NULL; 

If (root == null) return NULL; 

Node y  = null; 

If (z.left == null || z.right ==null) 

       Y = z; 

Else 

      Y = TreeSuccessor(ref node, z) ;

X = null ;

If (y.left != null)  

                X = y.left ;

else 

                x = y.right ;

If (x != NULL) 

                x.parent = y.parent ;

If (y.parent == NULL) 

                Root = x ;

 Else if (y = y.parent.left)

          then 

             y.parent.left = x ;

         else 

             y.parent.right = x ;

if (y != z )

    then z.data = y.data ;

return y 

} 

  

void TreeInsert(Node tree1, Node z) 

{ 

Node Y = NULL; 

Node x = tree1; 

While (x != NULL){ 

      Y = X; 

       If  (z.data  < x.data) 

           X= x.left; 

     Else 

           X = x.right;  

z.parent = y; 

if (y == NULL) 

        tree1 = Z; 

else if (z.data < y.data) 

             z = y.left; 

        else 

            z = y.right; 

} 

  

} 

Node Merge(Node tree1, Node tree2) 

{ 

Node current = tree2; 

While (current) 

{ 

Var root = TreeDelete(ref tree2, current); 

TreeInsert(ref tree1, root); 

Current = tree2; 

} 

Return tree1; 

}
Node TreeSuccessor(Node x)
{
If (x == null) return null;
If (x.right) return TreeMinimum(x.right);
Node y = x.parent;
While(y != null && y.right == x){
    X = y;
    Y = y.p;
}
Return y;
}

Node TreePredecessor(Node x)

{

If (x == null) return null;

If (x.left) return TreeMaximum(x.left);

Node y = x.parent;

While(y != null && y.left == x){

    X = y;

    Y = y.p;

}

Return y;

} 

Node TreeMinimum(node root)
{
If(root == null) return null;
Node current = root;
While(current && current.left)
       Current = current.left;
   Return current;
}

Node TreeMaximum(node root)
{
If(root == null) return null;
Node current = root;
While(current && current.right)
       Current = current.right;
   Return current;

}