BinarySearchTree.c

//12 a)

#include <stdio.h>
#include <stdlib.h>

typedef struct Tree{
    int data;
    struct Tree*left;
    struct Tree*right;
}Tree;

Tree*create(int val){
    Tree*newNode=(Tree*)malloc(sizeof(Tree));
    newNode->data=val;
    newNode->right=NULL;
    newNode->left=NULL;

    return newNode;
}

Tree*insert(Tree*root,int val){
    if(root==NULL){
        root=create(val);
        return root;
    }
    else if(val<root->data){
        root->left=insert(root->left,val);
    }
    else if(val>root->data){
        root->right=insert(root->right,val);
    }
    else{
        printf("Duplicate values not allowed!...\n");
    }
    return root;
}

void display(Tree*root,int level){
    if(root!=NULL){
        display(root->right,level+1);
        for(int i=0;i<level;i++){
            printf("    ");
        }
        printf("%d\n",root->data);
        display(root->left,level+1);
    }
}

void inorder(Tree*root){
    if(root!=NULL){
        inorder(root->left);
        printf("%d ",root->data);
        inorder(root->right);
    }
}

void preorder(Tree*root){
    if(root!=NULL){
        printf("%d ",root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(Tree*root){
    if(root!=NULL){
        postorder(root->left);
        postorder(root->right);
        printf("%d ",root->data);
    }
}

Tree*min(Tree*root){
    while(root->left!=NULL){
        root=root->left;
    }
    return root;
}

Tree*delete(Tree*root,int val){
    if(root==NULL){
        return root;
    }

    if(root!=NULL){
        if(val<root->data){
            root->left=delete(root->left,val);
        }
        else if(val>root->data){
            root->right=delete(root->right,val);
        }
        else{

            //Case A - root to delete is a leaf node
            if(root->right==NULL && root->left==NULL){
                free(root);
                return NULL;
            }

            //Case B - root to delete has on child
            else if(root->right==NULL){
                Tree*temp=root->left;
                free(root);
                return temp;
            }
            else if(root->left==NULL){
                Tree*temp=root->right;
                free(root);
                return temp;
            }

            //Case C - root to delete has two children
            else{
                Tree*temp=min(root->right);
                root->data=temp->data;
                root->right=delete(root->right,temp->data);
            }
        }
    }
    return root;
}

Tree*max(Tree*root){
    while(root->right!=NULL){
        root=root->right;
    }
    return root;
}

Tree* search(Tree*root,int val){
    if(root==NULL){
        printf("Search Unsuccessful! Key-> %d not found in tree!\n",val);
        return root;
    }
    if(root->data==val){
        printf("Search Successful!\nKey-> %d found in tree!\n",val);
        return root;
    }    
    else if(val<root->data){
        return search(root->left,val);
    }
    else{
        return search(root->right,val);
    }
}

int leaf(Tree*root){
    if(root==NULL){
        return 0;
    }
    else if(root->right==NULL && root->left==NULL){
        return 1;
    }
    else{
        return (leaf(root->right)+leaf(root->left));
    }
}

int height(Tree*root){
    if(root==NULL){
        return 0;
    }
    int left=height(root->left);
    int right=height(root->right);

    if(left>right){
        left+=1;
        return left;
    }
    else{
        return ++right;
    }
}
void main(){
    Tree*root=NULL;
    Tree*temp=NULL;
    int ch,val;
    for(;;){
        printf("\nENTER:\n1. To insert\n2. To display\n3. To perform inorder traversal\n4. To perform preorder traversal\n5. To perform postorder traversal\n6. To delete\n7. To find minimum element\n8. To find maximum element\n9. To search\n10. To find the number of leaf nodes\n11. To find the height of tree\n0. To EXIT\n");
        printf("Enter your choice from above: ");
        scanf("%d",&ch);

        switch(ch){
            case 1:
            printf("Enter the value to insert: ");
            scanf("%d",&val);
            root=insert(root,val);
            break;

            case 2:
            display(root,0);
            break;

            case 3:
            inorder(root);
            break;

            case 4:
            preorder(root);
            break;

            case 5:
            postorder(root);
            break;

            case 6:
            printf("Enter the value to delete: ");
            scanf("%d",&val);
            root=delete(root,val);
            break;

            case 7:
            if(root==NULL){
            printf("Tree is Empty...\n");
            break;
            }
            temp = min(root);
            printf("The most minimum element of the tree-> %d\n",temp->data);
            break;

            case 8:
            if(root==NULL){
            printf("Tree is Empty...\n");
            break;
            }
            temp = max(root);
            printf("The most minimum element of the tree-> %d\n",temp->data);
            break;

            case 9:
            if(root==NULL){
            printf("Tree is Empty...\n");
            break;
            }
            printf("Enter the value to search: ");
            scanf("%d",&val);
            search(root,val);
            break;

            case 10:
            if(root==NULL){
            printf("Tree is Empty...\n");
            break;
            }
            printf("Number of leaf nodes are: %d\n",leaf(root));
            break;

            case 11:
            printf("Height of tree: %d\n",height(root));
            break;

            case 0:
            printf("Exiting...\n");
            exit(0);

            default:
            printf("Invalid Choice! Please Enter Again!...\n");
        }

    }
}