BINARY SEARCH TREE

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

struct treenode;

typedef struct treenode *position;

typedef struct treenode *searchtree;

searchtree makeempty(searchtree T);

position find(int X,searchtree T);

position findmin(searchtree T);

position findmax(searchtree T);

searchtree insert(int X,searchtree T);

searchtree Delete(int X,searchtree T);

struct treenode

{

 int element;

 searchtree left;

 searchtree right;

}*root;

searchtree makeempty(searchtree T)

{

 if(T!=NULL)

 {

  makeempty(T->left);

  makeempty(T->right);

  free(T);

 }

 return NULL;

}

position find(int X,searchtree T)

{

 if(T==NULL)

   return NULL;

 if(X<T->element)

    return find(X,T->left);

 else

   if(X>T->element)

    return find(X,T->right);

 else

    return T;

}

position findmin(searchtree T)

{

 if(T==NULL)

   return NULL;

 else

   if(T->left==NULL)

    return T;

 else

   return findmin(T->left);

}

searchtree insert(int X,searchtree T)

{

 if(T==NULL)

 {

  T=(struct treenode*)malloc(sizeof(struct treenode));

  if(T==NULL)

   printf("\n Error");

  else

  {

   T->element=X;

   T->left=T->right=NULL;

  }

 }

 else

   if(X<T->element)

     T->left=insert(X,T->left);

   else

    if(X>T->element)

     T->right=insert(X,T->right);

  return T;

}

searchtree Delete(int X,searchtree T)

{

 position tmpcell;

 if(T==NULL)

   printf("\n Element not found");

 else

  if(X<T->element)

   T->left=Delete(X,T->left);

 else

  if(X>T->element)

   T->right=Delete(X,T->right);

 else

  if(T->left && T->right)

  {

   tmpcell= findmin(T->right);

   T->element=tmpcell->element;

   T->right=Delete(T->element,T->right);

  }

  else

  {

   tmpcell=T;

   if(T->left==NULL)

    T=T->right;

   else

    if(T->right==NULL)

     T=T->left;

    free(tmpcell);

   }

   return T;

}

void inorder(searchtree T)

{

 if(T!=NULL)

 {

  inorder(T->left);

  printf("%d\t",T->element);

  inorder(T->right);

 }

}

void main()

{

 int ch,value;

 root=NULL;

 clrscr();

 printf("\n 1.Insert 2. Delete 3. Display 4.Find ");

 do

 {

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

  scanf("%d",&ch);

  switch(ch)

  {

   case 1:

         printf("\n Enter a no. to insert:");

         scanf("%d", &value);

         root=insert(value,root);

         break;

   case 2:

         printf("\n Enter the no. to delete:");

         scanf("%d",&value);

         root=Delete(value,root);

         break;

   case 3:

         printf("\n Tree Elements\n");

         inorder(root);

         break;

   case 4:

         printf("\n Enter the element to find:");

         scanf("%d",&value);

         root=find(value,root);

         printf("\n The found element:%d",root->element);

         break;

   default:

         break;

  }

 }while(ch<5);

 getch();

}