Merge two binary search trees

How do you merge two binary search trees?

I googled about the solutions. Most solutions told me to convert both trees into linked lists. Merge the lists. Then create a tree from the elements of the list.

But why lists? Why can't we store the elements in an array? Because if the data of the tree is larger - not just integer keys, array manipulation becomes difficult.

But again, we need not convert both the trees into lists. We can convert one tree into list - a doubly linked list. Then insert the elements of this list into the other tree.

I tried this approach.

To convert a tree into a sorted doubly linked list

1. Create a doubly linked list. Let the prev and next links of nodes in this list be called left and right respectively. This way we can directly use the binary tree nodes in the list.
2. Use a static variable previousnode 
3. call the function recursively for left child of current node.
4. link current node to the previousnode
1. set next pointer of previousnode to current node. 
2. set previous pointer of current node to previous node
5. Now set this node as previousnode
6. call the function for right child of current node. 

If previousnode is NULL, it means you are visiting tree minimum, so set this node as head.

Here is the function to convert binary search tree to sorted doubly linked list. 

void convert_to_dll(NODEPTR nd,NODEPTR*headptr)
{
   static NODEPTR prevnode;
   if(nd!=NULL)
    {       
 convert_to_dll(nd->left,headptr);
        if(prevnode!=NULL){
           prevnode->right = nd;
           nd->left = prevnode;
        }
        else{
           *headptr = nd;
        }
        prevnode = nd; 
        convert_to_dll(nd->right,headptr);
     }
}

Next we need to take this list, extract one node at a time and insert the node in the other binary search tree.  

How do we extract nodes? Easiest way to do that is take head node (first node), insert this to BST. Move to next node in the list by saying head = head->next.

Please remember that, we need to set both links of the node to NULL before inserting it into BST.

1. set temp to head
2. insert temp into binary search tree
3. move to next node by using head = head->right. (right because we have used left for previous and right for next)
4. repeat the steps 1 to 3  as long as  head is not NULL. 

Here is the code for the same.

NODEPTR merge_bsts(NODEPTR root,NODEPTR head)
{
     while(head!=NULL)
     {
 NODEPTR temp = head;
 head = head->right;
        temp->left = temp->right = NULL;
 root = insert_node(root,temp);
      }
      return root;
}

Let us write a create 2 lists and use these functions.

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void convert_to_dll(NODEPTR nd,NODEPTR*headptr)
{
   static NODEPTR prevnode;
   if(nd!=NULL)
    {       
 convert_to_dll(nd->left,headptr);
        if(prevnode!=NULL){
           prevnode->right = nd;
           nd->left = prevnode;
        }
        else{
           *headptr = nd;
        }
        prevnode = nd; 
        convert_to_dll(nd->right,headptr);
     }
}
 
void print_dll(NODEPTR nd)
{
   NODEPTR temp = nd;
    while(nd)
      {
        printf("%d---->",nd->val);
        temp = nd; nd = nd->right;
       }
     printf("\nnow in reverse");
     nd = temp;
     while(nd)
      {
        printf("%d---->",nd->val);
        temp = nd; nd = nd->left;
       }
}

NODEPTR merge_bsts(NODEPTR root,NODEPTR head)
{
     while(head!=NULL)
     {
 NODEPTR temp = head;
 head = head->right;
        temp->left = temp->right = NULL;
 root = insert_node(root,temp);
      }
      return root;
}

void inorder(NODEPTR nd)
{
   if(nd!=NULL)
   { 
 inorder(nd->left);
 printf("%d ",nd->val);
        inorder(nd->right);
    }
}

int main()
{
       NODEPTR root=NULL,delnode,head; 
       NODEPTR root2 = NULL;
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       printf("Second bst:");
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root2 = insert_node(root2,newnode);
             }
       } while (n!=-1);
       head = NULL;
       convert_to_dll(root2,&head);
       print_dll(head);
       root  = merge_bsts(root,head); 
       inorder(root);
       return 0;
}