Thursday 6 February 2014

Merging of two Binary Search Trees

#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int info;
    struct node *left,*right;
}node;
node* insert(node *root, int info)
{
    if(root == NULL)
    {
        root = (node*)malloc(sizeof(node));
        root->left=root->right = NULL;
        root->info = info;
    }
    else if(root->info > info)
        root->left = insert(root->left, info);
    else
        root->right = insert(root->right, info);
    return root;
}
void inorder(node *root)
{
    if(root != NULL)
    {
        inorder(root->left);
        printf("%d\t",root->info);
        inorder(root->right);
    }
}
node* merge(node *root, node *root1)
{
    if(root!=NULL)
    {
        root->left=merge(root->left, root1);
        root->right=merge(root->right, root1);
        root1 = insert(root1, root->info);
        root = NULL;
        free(root);
    }
    return root;
}
int main()
{
    int i=0, element=0;
    char ans='Y';
    node *root1=NULL,*root2=NULL;

    //input in bst1
    printf("Enter elements in BST 1\n");
    while(ans == 'y' || ans == 'Y')
    {
        printf("Enter element: ");
        scanf("%d",&element);
        root1 = insert(root1, element);
        printf("do u want to add more element[Y/N]: ");
        fflush(stdin);
        ans = getchar();
    }
    ans = 'Y';
    i = 0;
    printf("\nEnter element  in BST 2\n");
    while(ans == 'y' || ans == 'Y')
    {
        printf("Enter element: ");
        scanf("%d",&element);
        root2 = insert(root2, element);
        printf("do u want to add more element[Y/N]: ");
        fflush(stdin);
        ans = getchar();
    }
    printf("Tree1\n");
    inorder(root1);
    printf("\nTree2\n");
    inorder(root2);

    printf("\n\n\nMerged tree is\n");
    root2 = merge(root2, root1);
    inorder(root1);
    inorder(root2);

    return 0;
}