Problem:9.1

Question: 

Exercise 1:

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left sub tree and insert the data. Otherwise, search for the empty location in the right sub tree and insert the data.

Exercise 2:

Search Operation

Whenever an element is to be searched, start searching from the root node. Then if the data is

less than the key value, search for the element in the left subtree. Otherwise, search for the

element in the right subtree. Follow the same algorithm for each node.

Exercise 3:

Traversal Operation

Perform Pre, Post and In-order traversal of BST

Solution: 

 #include<stdio.h>

#include<stdlib.h>

struct treeNode

{

    int data;

    //struct treeNode *root;

    struct treeNode *left;

    struct treeNode *right;

};

struct treeNode *creatingNode(int data)

{

    struct treeNode *temp;

    temp = (struct treeNode*) malloc(sizeof(struct treeNode));

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;

}

struct treeNode *insertion(struct treeNode *root, int data){

    if(root == NULL)

    {        return creatingNode(data);

    }

    if(data < root->data)

    {

        root->left = insertion(root->left, data);

    }

    if (data > root->data)

    {

        root->right = insertion(root->right, data);

    }

    return root;

}

void inorder(struct treeNode *root)

{

    if(root == NULL)

    {

        return;

    }

    inorder(root->left);

    printf("%d ", root->data);

    inorder(root->right);

}

void preorder(struct treeNode *root)

{

    if(root == NULL)

    {

        return;

    }

    printf("%d ", root->data);

    preorder(root->left);

    preorder(root->right);

}

void postorder(struct treeNode *root)

{

    if(root == NULL)

    {

        return;

    }

    postorder(root->left);

    postorder(root->right);

    printf("%d ", root->data);

}

struct treeNode *searchNode(struct treeNode *root, int data)

{

    if(root == NULL || root-> data == data)

    {

        return root;

    }

    if(root->data < data)

    {

        return searchNode(root->right, data);

    }

    else if(root->data > data)

    {

        return searchNode(root->left, data);

    }

}

int main()

{

    int data, choice;

    struct treeNode *root = NULL, *temp;

    while(1)

    {

        printf("-------------------------------------------------------------------\n");

        printf("                    WELCOME TO BINARY SEARCH TREE                  \n");

        printf("-------------------------------------------------------------------\n");

        printf("1. Insertion\n");

        printf("2. InOrder Traversal\n");

        printf("3. PreOrder Traversal\n");

        printf("4. PostOrder Traversal\n");

        printf("5. Search A Node\n");

        printf("0. Exit!!!\n");

        printf("-------------------------------------------------------------------\n");

        printf("\nEnter Your choice: ");

        scanf("%d", &choice);

        switch(choice)

        {

            case 1:

                printf("\nEnter data: ");

                scanf("%d", &data);

                root = insertion(root, data);

                break;

            case 2:

                inorder(root);

                printf("\nThe nodes are in InOrder Traversal!\n");

                break;

            case 3:

                preorder(root);

                printf("\nThe nodes are in PreOrder traversal!\n");

                break;

            case 4:

                postorder(root);

                printf("\nThe nodes are in PostOrder Traversal!\n");

                break;

            case 5:

                printf("\nEnter data for searching: ");

                scanf("%d", &data);

                temp = searchNode(root, data);

                if(temp == NULL)

                {

                    printf("\nSearch is incomplete!!!\n");

                }

                else

                {

                    printf("\nSearch is complete!!!\n");

                }

                break;

            case 6:

                printf("\nExited from the program!!!");

                exit(0);

            default:

                printf("\nInvalid choice! Try again!!!\n");

                break;

        }

    }

    return 0;

}