#define YES 1
#define NO 0
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
class tree
{
    private:
struct leaf
{
     int data;
     leaf *l;
     leaf *r;
};
struct leaf *p;

    public:


void findparent(int n,int &found,leaf* &parent);
void findfordel(int n,int &found,leaf *&parent,leaf* &x);
void add(int n);

void del(int n);
};







void tree::findparent(int n,int &found,leaf *&parent)
{
    leaf *q;
    found=NO;
     parent=NULL;

    if(p==NULL)
return;

    q=p;
    while(q!=NULL)
    {
if(q->data==n)
{
     found=YES;
     return;
}
if(q->data>n)
{
     parent=q;
     q=q->l;
}
else
{
     parent=q;
     q=q->r;
}
    }
}

void tree::add(int n)
{
    int found;
    leaf *t,*parent;
    findparent(n,found,parent);
    if(found==YES)
cout<< "\nSuch a Node Exists"<<endl;
    else
    {
t=new leaf;
t->data=n;
t->l=NULL;
t->r=NULL;

if(parent==NULL)
     p=t;
else
     parent->data > n ? parent->l=t : parent->r=t;
    }
}




void tree::findfordel(int n,int &found,leaf *&parent,leaf *&x)
{
    leaf *q;
    found=0;
    parent=NULL;
    if(p==NULL)
return;

    q=p;
    while(q!=NULL)
    {
if(q->data==n)
{
     found=1;
     x=q;
     return;
}
if(q->data>n)
{
     parent=q;
     q=q->l;
}
else
{
     parent=q;
     q=q->r;
}
    }
}




void tree::del(int num)
{
    leaf *parent,*x,*xsucc;
    int found;

    // If EMPTY TREE
    if(p==NULL)
    {
cout<<"\nTree is Empty";
return;
    }
    parent=x=NULL;
    findfordel(num,found,parent,x);
    if(found==0)
    {
cout<<"\nNode to be deleted NOT FOUND";
return;
    }

    // If the node to be deleted has 2 leaves
    if(x->l != NULL && x->r != NULL)
    {
parent=x;
xsucc=x->r;

while(xsucc->l != NULL)
{
     parent=xsucc;
     xsucc=xsucc->l;
}
x->data=xsucc->data;
x=xsucc;
    }

    // if the node to be deleted has no child
    if(x->l == NULL && x->r == NULL)
    {
if(parent->r == x)
     parent->r=NULL;
else
     parent->l=NULL;

delete x;
return;
    }

    // if node has only right leaf
    if(x->l == NULL && x->r != NULL )
    {
if(parent->l == x)
     parent->l=x->r;
else
     parent->r=x->r;

delete x;
return;
    }

    // if node to be deleted has only left child
    if(x->l != NULL && x->r == NULL)
    {
if(parent->l == x)
     parent->l=x->l;
else
     parent->r=x->l;

delete x;
return;
    }
}





int main()
{
    tree t;
    int i;
    srand((unsigned)time(0));
    int random[65536];
    for(int i=0; i<10; i++)
    {
        
        random[i] = (rand()%10)+1;
    //  n=random[i];
    }
for(i =0; i<10; i++)
{
t.add(random[i]);
}
for(i=0;i<10;i++)
{
  
    t.del(random[i]);
}  
  
            return 0;
}