Binary Search Tree (BST) program

#include<stdio.h>

#include<conio.h>

struct node {

int data;

struct node *left, *right;

};

typedefstruct node NODE;

NODE *root=NULL;

int count=1,count1=0;

void insertion() {

          NODE *p,*current,*follow;

          int n;

          p=(NODE *)malloc(sizeof(NODE));

          printf("\n enter the data");

          scanf("%d",&n);

          p->data=n;

          p->left=p->right=NULL;

          if(root==NULL)

                   root=p;

          else {

                   current=root;

                   follow=NULL;

          while(current!=NULL) {

                   follow=current;

                   if(p->data<current->data)

                             current=current->left;

                   else

                             current=current->right;

          }

          if(p->data<follow->data)

                   follow->left=p;

          else

                   follow->right=p;

          }

}

void level() {

          intx,level=0,value;

          NODE  *current=root;

          printf("\n enter the value");

          scanf("%d",&value);

          while(value!=current->data && current!=NULL) {

                   level++;

                   if(value<current->data)

                             current=current->left;

                   else

                             current=current->right;

          }

          if(current==NULL)

printf("\n specified node is not found");

          else

                   printf("\n the level of required node is %d",level);

}

void deletion() {

          NODE *p, *q, *f,*s,*rp;

          int key;

          p=root;

          q=NULL;

          printf("\n enter the data to be deleted from BST");

          scanf("%d",&key);

          while(p!=NULL&&p->data!=key) {

                   q=p;

          if(key<p->data)

                   p=p->left;

          else

                   p=p->right;

          }

          if(p==NULL)

                   printf("\n key is not found");

          if(p->left==NULL)

                   rp=p->right;

          else if(p->right==NULL)

                   rp=p->left;

          else {

                   f=p;

                   rp=p->right;

                   s=rp->left;

          while(s!=NULL) {

                   f=rp;

                   rp=s;

                   s=rp->left;

          }

          if(f!=p) {

                   f->left=rp->right;

                   rp->right=p->right;

          }

          rp->left=p->left;

          if(q==NULL)

                   root=rp;

          else if(p==(q->left))

                   q->left=rp;

          else

                   q->right=rp;

          }

}

voidcountn(NODE *p) {

          if(p!=NULL) {

                   if(p->left!=NULL) {

                             count++;

                   printf("count=%d",count);

                             countn(p->left);

                   }

                   if(p->right!=NULL) {

                             count++;

          printf("\n count=%d",count);

                             countn(p->right);

                   }

//count++;

//printf("\n no of nodes are %d",count);

          }

}

void leaf(NODE *p) {

          if(p!=NULL) {

                   leaf(p->left);

if(p->left==NULL&&p->right==NULL) {

                             count1++;

                             printf( "\n count=%d data=%d",count1,p->data);

                   }

                   leaf(p->right);

          }

}

voidinorder(NODE *p) {

          if(p!=NULL) {

                   inorder(p->left);

                   printf("%d\t ",p->data);

                   inorder(p->right);

          }

}

void main() {

          char ch1;

          intch;

          clrscr();

          printf("\n 1.INSERTION \n 2.DELETION \n 3.COUNT \n 4.LEAFNODE \n 5.INORDER\n 6:level");    

          do {

          printf("\n enter your choice:");

                   scanf("%d",&ch);

                   switch(ch) {

          case 1:insertion();       break;

          case 2:deletion();        break;

          case 3:                                                         if(root==NULL)

                   printf("No data");

                   else                                                    countn(root);

                    break;

          case 4:

                   if(root==NULL)                                   printf("No data");                               else

                             leaf(root);

                             break;

          case 5:

                             if(root==NULL)

                             printf("No data");

                             else                                                   inorder(root);

                             break;

          case 6:level();break;

                   }

          } while(ch1!=7);

}