#include<iostream>
using namespace std;
struct node{
 int info;
 node *left,*right;
}*root=NULL;
struct Queue{
 node* data;
 Queue *link;
}*front=NULL,*rear=NULL;
void AddNode(int item)
{
 node *temp=new node;
 temp->info=item;
 temp->left=NULL;
 temp->right=NULL;
 if(root==NULL)
 {
  root=temp;
 }
 else
 {
  node *ptr1=NULL;
  node *ptr=root;
  while(ptr!=NULL)
  {
   ptr1=ptr;
   if(ptr->info<item)
      {
        ptr=ptr->right;
      }
      else
      {
        ptr=ptr->left;
      }
  }
  if(ptr1->info<item)
  {
   ptr1->right=temp;
  }
  else
  {
   ptr1->left=temp;
  }
 } 
}
void Inorder(node *root)
{
 if(root!=NULL)
 {
  Inorder(root->left);
  cout<<root->info<<"t";
  Inorder(root->right);
 }
}
void Preorder(node *root)
{
 if(root!=NULL)
 {
  cout<<root->info<<"t";
  Preorder(root->left);
  Preorder(root->right);
 }
}
void Postorder(node *root)
{
 if(root!=NULL)
 {
  Postorder(root->left);
  Postorder(root->right);
  cout<<root->info<<"t";
 }
 
}
void Insert(node* item)
{
 Queue *ptrr=new Queue;
 ptrr->data=item;
 ptrr->link=NULL;
 if(front==NULL)
 {
  front=rear=ptrr;
 }
 else
 {
  rear->link=ptrr;
  rear=ptrr;
 }
}
node* Delete()
{
 node* item=front->data;
 if(front!=NULL)
 {
  front=front->link;
  return item;
 }
 else
 {
  return 0;
 }
}
int Levelorder(node *root)//level oreder traversal
{
 node *t=root;
 if(!t)
 {
  return 0;
 }
 Insert(t);
 while(front!=NULL)
 {
  t=Delete();
  cout<<t->info<<"t";
  if(t->left)
  {
   Insert(t->left);
  }
  if(t->right)
  {
   Insert(t->right);
  }
 }
}
void search(node *root,int item)
{
 node *temp=root;
 if(temp==NULL)
 {
  cout<<"nthere is no element in the treen";
 }
 else
 {
  while(temp)
  {
      if(temp->info==item)
      {
       cout<<"nitem is available in the treen";
       break;
      }
      else if(temp->info<item)
      {
       temp=temp->right;
      }
      else
      {
       temp=temp->left;
      }
      if(temp==NULL)
      {
       cout<<"nItem is not available in the treen";
      }
    }
 }
}
void Del(int item)
{
 node *ptr,*par;
 node *par_replacement,*replacement;
 node *childptr;
 par=NULL;
 ptr=root;
 int is_left=0;
 while(ptr!=NULL)
 {
  if(item==ptr->info)
  {
   break;
  }
  else if(item<ptr->info)
  {
   par=ptr;
   is_left=1;
   ptr=ptr->left;
  }
  else
  {
   par=ptr;
   is_left=0;
   ptr=ptr->right;
  }
 }
 if(ptr==NULL)
 {
  cout<<"nnode with value "<<item<<" does not exist in the treen";
 }
 else if((ptr->left==NULL)&&(ptr->right==NULL))
 {
  if(par==NULL)
  {
   free(root);
  }
  else
  {
   free(ptr);
   if(is_left)
   {
    par->left=NULL;
   }
   else
   {
    par->right=NULL;
   }
  }
 }
 else if((ptr->right==NULL)||(ptr->left==NULL))
 {
  if(ptr->left!=NULL)
  {
   childptr=ptr->left;
  }
  else
  {
   childptr=ptr->right;
  }
     if(par==NULL)
     {
      root=childptr;
      free(ptr);
  }
  else
  {
   if(is_left)
   {
    par->left=childptr;
   }
   else
   {
    par->right=childptr;
   }
   free(ptr);
  }
 }
 else
 {
  par_replacement=ptr;
  replacement=ptr->left;
  is_left=1;
  while(replacement->right!=NULL)
  {
   par_replacement=replacement;
   replacement=replacement->right;
   is_left=0;
  }
  ptr->info=replacement->info;
  if(is_left)
  {
   ptr->left=replacement->left;
   free(replacement);
  }
  else
  {
   par_replacement->right=replacement->left;
   free(replacement);
  }
 }
 
}
int main()
{
 int item,choice;
 while(1)
 {
  cout<<"n1. Add a Valuen2. Inorder Traversaln3. Preorder Traversaln4. Postorder Traversaln";
  cout<<"5. Levelorder Traversaln6. Find Elemetsn7. Deleten8. Exitn";
  cout<<"nEnter Your Choice";
  cin>>choice;
  switch(choice)
  {
   case 1:
    cout<<"nENter the value to be addedd";
     cin>>item;
     AddNode(item);
     break;
   case 2:
    Inorder(root);
    cout<<"n";
    break;
   case 3:
    Preorder(root);
    cout<<"n";
    break;
   case 4:
    Postorder(root);
    cout<<"n";
    break;
   case 5:
    Levelorder(root);
    cout<<"n";
    break;
   case 6:
    cout<<"Enter the number to be searched";
    cin>>item;
    search(root,item);
    break;
   case 7:
    cout<<"Enter the element you want to delete";
    cin>>item;
    Del(item);
    break;
   case 8:
    exit(0);
  }
 }
 return 0;
}