C Programming Binary Search Tree (BST) implementation insert and display it inorder, preorder and postorder

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

typedef struct binary_tree
{
    struct binary_tree *left_sub_tree;
    int val;
    struct binary_tree *right_sub_tree;
} tree;

tree *root;

tree *insert(tree *r, tree *n)
{
    if(r == NULL){
        r = n;
        r->left_sub_tree = NULL;
        r->right_sub_tree = NULL;
        return;
    }

    else if(n->val < r->val)
        r->left_sub_tree = insert(r->left_sub_tree,n);
    else if(n->val > r->val)
        r->right_sub_tree = insert(r->right_sub_tree,n);

    else printf("\n\nError!!!");
    return r;
}

tree **search(tree *r, tree **prev, int *s)
{
    if(r){
        if(s < r->val){
            prev = &r->left_sub_tree;
            r = *search(r->left_sub_tree, prev, s);
        }
    }

    else if(s > r->val){
        prev = &r->right_sub_tree;
        r = *search(r->right_sub_tree, prev, s);
    }

    else if(s == r->val)
        return prev;

    return 0;
}

del()
{
    tree **p, *q, **prev;
    int d_key;
    p = (struct binary_tree **)malloc(sizeof(struct binary_tree));
    printf("\n\nEnter element to be deleted: ");
    scanf("%d", &d_key);
    prev = &root;
    p = search(root, prev, d_key);

    if(*p == NULL){
        printf("\n\nCannot delete empty node.");
        return 0;
    }

    else if((*p)->right_sub_tree == NULL){
        q = *p;
        (*p) = (*p)->left_sub_tree;
    }

    else if((*p)->left_sub_tree == NULL){
        q = (*p);
        (*p) = (*p)->right_sub_tree;
    }

    else {
        for(q = (*p)->right_sub_tree ; q->left_sub_tree ; q = q->left_sub_tree);
        q->left_sub_tree = (*p)->left_sub_tree;
        q = (*p);
        (*p) = (*p)->right_sub_tree;
    }

    printf("%d is deleted", d_key);
    free(q);
    return 0;

}

tree *inorder(tree *r)
{
    if(r){
        inorder(r->left_sub_tree);
        printf("\n\t %d ", r->val);
        inorder(r->right_sub_tree);
    }
    return 0;
}

tree *preorder(tree *r)
{
    if(r){
        printf("\n\t %d ", r->val);
        preorder(r->left_sub_tree);
        preorder(r->right_sub_tree);
    }
    return 0;
}

tree *postorder(tree *r)
{
    if(r){
        preorder(r->left_sub_tree);
        preorder(r->right_sub_tree);
        printf("\n\t %d ", r->val);
    }
    return 0;
}


void display()
{
    printf("\n\n\tThis is inorder display\n");
    inorder(root);
    getch();

    printf("\n\n\tThis is preorder display\n");
    preorder(root);
    getch();

    printf("\n\n\tThis is postrder display\n");
    postorder(root);
    getch();

}

void main()
{
    int ch, s_key, d_key;
    tree *ptr;

    for(;;){
        printf("\n1.Insert\n2.Display\n");
        scanf("%d",&ch);

        switch(ch)
        {
            case 1:
                ptr = (struct binary_tree*)malloc(sizeof(struct binary_tree));
                printf("Enter : ");
                scanf("%d", &ptr->val);
                ptr->left_sub_tree = ptr->right_sub_tree = NULL;
                root = insert(root,ptr);
                break;

            case 2:
                display();
                break;

            case 3:
                exit(0);


        }
    }
}


Output:

Download Source File