Operations on BST

/*

    Author :    Asim Krishna Prasad

    Program to perform the following operatios on a binary-search-tree :
    * insertion
    * pre-, in-, post- & level- order traversals
    * deletion

*/

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

#define scan(a)     scanf("%d", &a)
#define print(a)    printf("%d", a)
#define nline       printf("\n")
#define fl(i,a,b)   for(i=a; i<b; i++)
#define rev(i,a,b)  for(i=a; i>=b; i--)
#define sspace      printf(" ")

typedef struct node
{
    int data;
    struct node* left, *right;
}node;

node* root;

node* insert(node* curr, int ndata)
{
    if(curr==NULL)
    {
        node *temp;
        temp=(node *)(malloc(sizeof(node)));
        temp->data=ndata;
        temp->left=temp->right=NULL;
        curr=temp;
        return curr;
    }
    else if(ndata>curr->data)
    {
        curr->right=insert(curr->right,ndata);
    }
    else
    {
        curr->left=insert(curr->left,ndata);
    }
    return curr;
}

node* getminnode(node* curr)
{
    if(curr->left==NULL)
        return curr;
    getminnode(curr->left);
}

node* delete(node* curr, int key)
{
    if(curr==NULL)
        return curr;

    if(key<curr->data)
        curr->left=delete(curr->left,key);
    else if(key>curr->data)
        curr->right=delete(curr->right,key);
    else
    {
        if(curr->left==NULL)
        {
            node* temp=curr->right;
            free(curr);
            return temp;
        }
        if(curr->right==NULL)
        {
            node* temp=curr->left;
            free(curr);
            return temp;
        }

        node* temp=getminnode(curr->right);
        curr->data = temp->data;
        curr->right = delete(curr->right, temp->data);
    }
    return curr;
}

void inorder(node* curr)
{
    if(curr==NULL)
        return;
    inorder(curr->left);
    print(curr->data); sspace;
    inorder(curr->right);
    return;
}

void postorder(node* curr)
{
    if(curr==NULL)
        return;
    postorder(curr->left);
    postorder(curr->right);
    print(curr->data); sspace;
    return;
}

void preorder(node* curr)
{
    if(curr==NULL)
        return;
    print(curr->data); sspace;
    preorder(curr->left);
    preorder(curr->right);
    return;
}

int max(int a, int b)
{
    if(a>b)
        return a;
    return b;
}

int getheight(node* curr)
{
    if(curr==NULL)
        return 0;
    return max(getheight(curr->left)+1, getheight(curr->right)+1);
}

void levelorder(node* curr, int level, int target)
{
    if(level>target || curr==NULL)
        return;
    if(level==target)
        print(curr->data);
    levelorder(curr->left,level+1,target);
    levelorder(curr->right,level+1,target);
    return;
}

int main()
{
    int i, j, k, n, temp;
    int ndata;
    printf("Enter the number of elements to be inserted : ");
    scan(n);
    printf("Enter the elements to be inserted, one-by-one : ")
    fl(i,0,n)
    {
        scan(ndata);
        root=insert(root,ndata);
    }
    print(root->data); nline;
    printf("Traversals :\n");
    inorder(root); nline;
    preorder(root); nline;
    postorder(root); nline;
    int hlimit=getheight(root);
    print(hlimit);
    fl(i,0,hlimit)
    {
        levelorder(root,0,i);
    }
    nline;
    printf("Enter the number of nodes you want to delete : ");
    scan(n);
    fl(i,0,n)
    {
        printf("Enter the key to be deleted : ");
        scan(k);
        delete(root,k);
        printf("Inorder traversal after deletion : ");
        inorder(root); nline;
    }
    nline;
    return 0;
}