5 Binary - Insertion Search & Deletion

#include<iostream>
#include<stdlib.h>

using namespace std;

struct node
{
int d;
struct node *left;
struct node *right;
};

struct node *root;


void init();
void empty();
int insert(int);
void search(int);
void remove(int);
 
void init()
{
root=(struct node *)malloc(sizeof(struct node));
root=NULL;
}

int insert(int x)
{
struct node *p,*previous,*current;
p=(struct node *)malloc(sizeof(struct node));
 if (p==NULL)
 {
 cout<<"\nOut of Memory";
 return 0;
 }
p->d=x;
p->left=NULL;
p->right=NULL;
 if(root==NULL)
 {
 root=p;
 return 1;
 }
previous=NULL;
current=root;

 while (current!=NULL)
 {
 previous=current;
  if (p->d<current->d)
  current=current->left;
  else
  current=current->right;
 }

 if(p->d<previous->d)
 previous->left=p;
 else
 previous->right=p;

return 1;
}

void remove(int x)
{
struct node *ptr=root, *parent = NULL, *t1, *t2, *temp;
 while(ptr!=NULL && ptr->d!=x)
 {
 parent=ptr;
 if(x<ptr->d)
  ptr=ptr->left;
 else
  ptr=ptr->right;
 }

 if(ptr==NULL)
 {
 cout<<"\nDelete Element Not found";
 return;
 }
 
 if(ptr->left==NULL)
  t1=ptr->right;
 else if(ptr->right==NULL)
  t1=ptr->left;
 else
 {
 t2=ptr;
 t1=ptr->right;
 temp=t1->left;
 
  while(temp!=NULL)
  {
  t2=t1;
  t1=temp;
  temp=t1->left;
  }
 
  if(t2!=ptr)
  {
  t2->left=t1->right;
  t1->right=ptr->right;
  }

  t1->left=ptr->left;
 }

 if(parent==NULL)
  root=t1;
 else
 {
  if(parent->left==ptr)
  parent->left=t1;
  else
  parent->right=t1;
 }

free(ptr);
}


void search(int sno)
{
struct node*t;
t=(struct node *)malloc(sizeof(struct node));
t=root;
 while(t!=NULL && t->d !=sno)
 {
  if(t->d>sno)
  { t=t->left; }
  else
  { t=t->right; }
 }

 if(t)
 cout<<"\nThe Search Element is Present";
 else
 cout<<"\nElement not Present";
}

int main()
{
int c,no,x;
init();

 do
 {
 cout<<"\n1.Insert";
 cout<<"\n2.Deletion";
 cout<<"\n3.Search";
 cout<<"\n4.Exit";
 cout<<"\nEnter Your Choice:\t";
 cin>>c;
 
  switch(c)
  {
  case 1:cout<<"\nEnter the Element to Insert:\t";
         cin>>no;
         x=insert(no);
          if(x==1)
          cout<<"\nsucessful Insertion";
          else
          cout<<"\nError in insertion";
         break;
  case 2:cout<<"\nEnter the Element to Delete:";
         cin>>x;
         remove(no);
         break;
  case 3:cout<<"\nEnter the Element to Search: \t";
         cin>>no;
         search(no);
         break;
  case 4: exit(0); break;
  default: cout<<"\nEnter Any No. Between 1-7"; break;
  }
 }while(c!=4);
return 0;
}