Merge Two Balanced Binary Search Trees

PROBLEM :

Merge Two Balanced Binary Search Trees

You are given two balanced binary search trees e.g., AVL or Red Black Tree. Write a function that merges the two given balanced BSTs into a balanced binary search tree. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------


/*
typedef struct BST
{
int info ;
struct BST *left ;
struct BST *right ;
}tree ;                                 */

tree* create_tree(tree *,int ) ;
void preorder_input_2ndtree(tree *,tree **) ;

tree * Merge_2BST()
{
tree *root1,*root2 ;
int no1,no2,i,ele;
root1=NULL ;
root2=NULL ;

cout<<"\n how many elemets in the first list" ;
cin>>no1 ;
cout<<"\n enter the elements " ;
for(i=0;i<no1;i++)
{
cin>>ele ;
root1=create_tree(root1,ele) ;
}

cout<<"\n how many elemets in the second list" ;
cin>>no2 ;
cout<<"\n enter the elements " ;
for(i=0;i<no2;i++)
{
cin>>ele ;
root2=create_tree(root2,ele) ;
}

preorder_input_2ndtree(root1,&root2) ;
return root2 ;
}

tree* create_tree(tree *root,int data)
{
tree *node ;
node=(tree*)malloc(sizeof(tree)) ;
node->info=data ;
node->left=NULL ;
node->right=NULL ;

if(root==NULL)
{
root=node ;
return root ;
}
else
{
if(root->info>=data)
root->left=create_tree(root->left,data) ;
else
root->right=create_tree(root->right,data) ;
}
return root ;
}

void preorder_input_2ndtree(tree *root1,tree **root2)
{
if(root1==NULL)
return ;
(*root2)=create_tree((*root2),root1->info) ;
preorder_input_2ndtree(root1->left,&(*root2)) ;
preorder_input_2ndtree(root1->right,&(*root2)) ;
}

-------------------------------------------------------------------------------
BETTER APPROCH :
-------------------------------------------------------------------------------

/*
typedef struct BST
{
int info ;
struct BST *left ;
struct BST *right ;
}tree ;                                 */


tree * Merge_2BST()
{
tree *root1,*root2 ;
int no1,no2,i,ele;
root1=NULL ;
root2=NULL ;

cout<<"\n how many elemets in the first list" ;
cin>>no1 ;
cout<<"\n enter the elements " ;
for(i=0;i<no1;i++)
{
cin>>ele ;
root1=create_tree(root1,ele) ;
}

cout<<"\n how many elemets in the second list" ;
cin>>no2 ;
cout<<"\n enter the elements " ;
for(i=0;i<no2;i++)
{
cin>>ele ;
root2=create_tree(root2,ele) ;
}

int a1[no1],a2[no2],a[no1+no2] ;
i=0 ;
inorder_array_fill(root1,a1,&i) ;
i=0 ;
inorder_array_fill(root2,a2,&i) ;

int x,y,k ;
x=0 ;
y=0 ;
k=0 ;

while(x!=no1&&y!=no2)
{
if(a1[x]<a2[y])
a[k++]=a1[x++] ;
else if(a1[x]>a2[y])
a[k++]=a2[y++] ;
else
{
a[k++]=a1[x++] ;
a[k++]=a2[y++] ;
}
}
while(x!=no1)
a[k++]=a1[x++] ;
while(y!=no2)
a[k++]=a2[y++] ;

tree *root=NULL ;
root=convert_BST_array(a,0,k-1) ;

return root ;
}

void inorder_array_fill(tree* root,int a[],int *s)
{
    if(root==NULL)
        return  ;
     
    inorder_array_fill(root->left,a,&(*s)) ;
    a[(*s)++]=root->info ;
    inorder_array_fill(root->right,a,&(*s)) ;
 
}

tree * convert_BST_array(int a[],int start,int end)
{
    if(start>end)
        return NULL;
       
    int mid ;
    mid=(start+end)/2 ;
    tree *root ;
   
    root=(tree*)malloc(sizeof(tree)) ;
    root->info=a[mid] ;
    root->left=convert_BST_array(a,start,mid-1) ;
    root->right=convert_BST_array(a,mid+1,end) ;
   
    return root ;
}    

---------------------------------------------------------------------------------