DS (II) Assignment 1: Set B- a)

a) Write a C program which uses Binary search tree library and implements following function with recursion:

T copy(T) – create another BST which is exact copy of BST which is passed as parameter.

int compare(T1, T2) – compares two binary search trees and returns 1 if they are equal and 0 otherwise.

Solution:

#include<stdio.h>

#include"bst.h"

struct node* copyBinaryTree(struct node *root)

{

    if(root == NULL)

        return NULL;

    /* create a copy of root node */

    struct node* newNode = (struct node*)malloc(sizeof(struct node));

    newNode->data=root->data;

    newNode->left=newNode->right=NULL;

    /* Recursively create copy of left and right sub tree */

    newNode->left = copyBinaryTree(root->left);

    newNode->right = copyBinaryTree(root->right);

    /* Return root of copy tree */

    return newNode;

}

int compare(struct node* root1, struct node* root2)

{

    if (root1 == NULL && root2 == NULL)

        return 1;

   // If any one of the tree is non-empty and other is empty, return false

    else if (root1 != NULL && root2 == NULL)

        return 0;

    else if (root1 == NULL && root2 != NULL)

        return 0;

   else { // Check if current data of both trees equal and recursively check for left and right subtrees

 if(root1->data==root2->data&&compare(root1->left,root2->left)&&compare(root1->right,root2->right))

            return 1;

        else

            return 0;

    }

}

void main()

{

    struct node *root, *copy, *root1;

    int ch,count, val;

    root=NULL;

    root1=NULL;

    while(1)

    {

        printf("\nBST OPERATIONS ---");

        printf("\n1 - Create BST\n");

        printf("2 - BST Copy\n");

        printf("3 - Compare Two BST\n");

        printf("4 - Inorder Traversal\n");

        printf("5 - Exit\n");

        printf("\nEnter your choice : ");

        scanf("%d", &ch);

        switch (ch)

        {

            case 1:

            while(1)

            {

                printf("\nEnter The data");

                    scanf("%d", &val);

                    if(val==0)

                       break;

                    else

                    {

               root=create(root, val);

            }

        }

            break;

            case 2:

printf("\nOriginal Tree\n");  

        inorder(root);

copy = copyBinaryTree(root);

    printf("\nCopy Tree\n");

    inorder(copy);

        break;

            case 3:

printf("\nCreating 2nd BST\n");  

                while(1)

            {

                printf("\nEnter The data");

                    scanf("%d", &val);

                    if(val==0)

                        break;

                    else

                    {

                root1=create(root1, val);

            }

        }

        printf("\n2nd BST is\n");  

            inorder(root);

        if(compare(root,root1))

            printf("Both BSTs are identical");

    else

            printf("BSTs are not identical");

        break;

            case 4:    

                inorder(root);

                break;

            case 5:    

                exit(0);

            default :     

           printf("Wrong choice, Please enter correct choice  ");

           break;    

        }

    }

}

Library Function ( .h file )
NOTE: save file name as ' btree.h'. 

 

#include<stdio.h>
#include<malloc.h>
struct node
{
    int data;
    struct node *left, *right;
};
struct node *create(struct node *root, int x)
{
    if(root==NULL)
    {
        root=(struct node*)malloc(sizeof(struct node));
        root->data=x;
        root->left=root->right=NULL;
        return(root);
    }
    else if(x<root->data)
    {
        root->left=create(root->left, x);           
    }
    else
        root->right=create(root->right, x);
    return(root);
}
struct node *insert(struct node *root, int key) {
  // Return a new node if the tree is empty
  if (root == NULL)
  {
          root=(struct node*)malloc(sizeof(struct node));
        root->data=key;
        root->left=root->right=NULL;
        return(root);
  }
  // Traverse to the right place and insert the node
  if (key < root->data)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);
  return root;
}
void preorder(struct node *root)
{
    if(root!=NULL)
    {
        printf(" %d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
void postorder(struct node *root)
{
    if(root!=NULL)
    {
        postorder(root->left);
        postorder(root->right);
        printf(" %d ", root->data);
    }
}
void inorder(struct node *root)
{
    if(root!=NULL)
    {
        inorder(root->left);
        printf(" %d ", root->data);
        inorder(root->right);
    }
}
struct node *searchBST(struct node *root, int data)
{
    if(root==NULL)
    {
        return(NULL);
    }
    if(root->data==data)
    {
        return(root);
    }
    else if(data<root->data)
        return(searchBST(root->left,data));
    else
        return(searchBST(root->right,data));
}