mycode

#include <iostream>
#include<stack>
#include <queue>

class node
{
    public:
    int data;
    node* lchild;
    node* rchild;
};

using namespace std;


class bst
{
    private:
        node *root;
        int height(node* p);
        int lsuc(node *t);
        int rsuc(node *t);
    public:

        bst();
        void insert(int x);
        node* search(int x);
        node* rsearch(int x, bool y=1);
        node* rinsert(int x, node* t=nullptr, bool y=1);
        node* Delete(int x, node* t=nullptr,bool y=1);
        ~bst();

};

 inline bst::bst()
        {
            root=nullptr;
        }


void bst::insert(int x)
        {
            node *ptr = new node;
            ptr->data=x;
            ptr->lchild = ptr->rchild = nullptr;

            if(root==nullptr)
            {
                root=ptr;
                return;
            }
            node* t=root;
            while(1)
            {
                if(t->data==x)
                return;

                else if (t->data>x  && t->lchild!=nullptr)
                {
                    t=t->lchild;
                }
                else if(t->data<x  && t->rchild!=nullptr)
                {
                    t=t->rchild;
                }
                else break;
            }
            if(t->data>x)
                t->lchild=ptr;
            else
                t->rchild=ptr;
        }






    node* bst::rinsert(int x,node *t,bool y)
        {

           if(y==1)
            t=root;

            if(t==nullptr)
            {
                 node *ptr = new node;
                ptr->data=x;
                ptr->lchild = ptr->rchild = nullptr;

                 if(root==nullptr)
                    root=ptr;

                return ptr;
            }
            if(t->data==x)
                    return t;


            if (t->data>x)
                {
                    t->lchild=rinsert(x,t->lchild,0);
                }
                else if(t->data<x)
                {
                     t->rchild=rinsert(x,t->rchild,0);
                }
                return t;
        }

        node* bst::search(int x)
        {
            node *t=root;
            while(t!=nullptr)
            {
                if(t->data==x)
                    return t;
                else if(t->data>x)
                {
                    t=t->lchild;
                }
                    else
                        t=t->rchild;
            }
            return nullptr;
        }


         node* bst::rsearch(int x,bool y)
        {
            static node *t;

            if(y==1)
            t=root;

            if(t!=nullptr)
            {
                if(t->data==x)
                    return t;
                else if(t->data>x)
                {
                    t=t->lchild;
                    return rsearch(x,0);
                }
                    else
                        t=t->rchild;
                    return rsearch(x,0);
            }
            else return nullptr;
        }


         bst::~bst()

            {
                 queue<node*> q;
                q.push(root);
                node* t;
                while(!q.empty())
                {
                     t=q.front();
                     q.pop();


                if (t->lchild!=nullptr)
                    q.push(t->lchild);

                  if (t->rchild!=nullptr)
                    q.push(t->rchild);

                delete t;
                }
            }

            int  bst::height(node* t)
            {
                if (t==nullptr)
                    return 0;
                return height(t->lchild)>height(t->rchild)?height(t->lchild+1):height(t->rchild+1);
            }

            int bst::lsuc(node *t)
            {
                node *p=t->lchild;
                while(p->rchild!=nullptr)
                {
                    p=p->rchild;
                }
                return p->data;
            }

            int bst::rsuc(node *t)
            {
                node *p=t->rchild;
                while(p->lchild!=nullptr)
                {
                    p=p->lchild;
                }
                return p->data;
            }



            node* bst::Delete(int x, node* t,bool y)
            {
                if(y==1)
                    t=root;

                    if(t==nullptr)
                        {
                            cout<<"i am in block 1\n";
                            return t;
                        }

                if(x>t->data)
                {
                    cout<<"i am in block 2\n";
                    t->rchild=Delete(x,t->rchild,0);
                }

                else if(x<t->data)
                {
                    cout<<"i am in block 3\n";
                    t->lchild=Delete(x,t->lchild,0);
                }

                else
                {
                    if(t->lchild==nullptr && t->rchild==nullptr)
                    {
                        cout<<"i am in block 4\n";
                        delete t;
                        t=nullptr;
                        return t;
                    }

                    if(height(t->lchild)>height(t->rchild))
                    {
                         cout<<"i am in block 5\n";
                        int z=lsuc(t);
                         t->data=z;
                        t->lchild=Delete(z,t->lchild,0);
                    }
                    else
                    {
                         cout<<"i am in block 6\n";
                        int z=rsuc(t);
                         t->data=z;
                        t->rchild=Delete(z,t->rchild,0);
                    }
                }
                return t;
            }


int main()
{

    bst test;

    test.rinsert(45);
       test.rinsert(35);
       test.rinsert(25);
    test.Delete(35);


    return 0;
}