#include<iostream>
using namespace std;
struct node{
 int info;
 node *left,*right;
};
node* NewNode(int item)
{
 node *temp=new node;
 temp->left=NULL;
 temp->right=NULL;
 temp->info=item;
 return(temp);
}
int search(node *temp,int item)
{
 if(temp)
 {
  if(item==temp->info)
     {
      return 1;
     }
     else if(item<temp->info)
     {
      search(temp->left,item);
     }
     else
     {
      search(temp->right,item);
     }
 }
}
node* minvalue(node *ptr)
{
 while(ptr->left)
 {
  ptr=ptr->left;
 }
 return ptr;
}
node *deletee(node *temp,int item)
{
 if(temp==NULL)
 {
  return temp;
 }
 if(item<temp->info)
 {
  temp->left=deletee(temp->left,item);
 }
 else if(item>temp->info)
 {
  temp->right=deletee(temp->right,item);
 }
 else
 {
  node *ptr;
  if((temp->left==NULL)&&(temp->right==NULL))
  {
   
   ptr=NULL;
   temp=ptr;
   free(temp);
   
  }
  else if((temp->left==NULL)||(temp->right==NULL))
  {
   if(temp->left)
   {
    ptr=temp->left;
   }
   else if(temp->right)
   {
    ptr=temp->right;
   }
   free(temp);
   return ptr;
  }
  else
  {
   node *ptr=minvalue(temp->right);
   temp->info=ptr->info;
   temp->right=deletee(temp->right,ptr->info);
  }
 }
}


node* insert(node *ptr,int data)
{
 if(ptr==NULL)
    {
     ptr=NewNode(data);
     return ptr;
 }
 else if(!search(ptr,data))
 {
     if(data<ptr->info)
     {
      ptr->left=insert(ptr->left,data);
     }
     else
     {
      ptr->right=insert(ptr->right,data);
     }
 }
 
 return ptr;
}
void inorder(node *root)
{
 if(root)
 {
  inorder(root->left);
  cout<<root->info<<"t";
  inorder(root->right);
 }
}
int main()
{
 node *root=NULL;
 root=insert(root,44);
 root=insert(root,76);
 root=insert(root,86);
 root=insert(root,36);
 root=insert(root,66);
 root=insert(root,16);
 root=insert(root,26);
 root=insert(root,96);
 inorder(root);
 int x=search(root,366);
 cout<<"nn"<<x<<"n";
 root=insert(root,76);
 inorder(root);
 root=deletee(root,76);
 cout<<"n";
 inorder(root);
 cout<"nn";
 LabelOrder(root);
 return 0;
}