#include<iostream>
#include<queue>
using namespace std;

class agac
{
private:
    struct node
    {
        int data;
        node* sol;
        node* sag;
    };

    node* root;

    node* ilk(node* t)
    {
        if(t == NULL)
            return NULL;
        {
            ilk(t->sol);
            ilk(t->sag);
            delete t;
        }
        return NULL;
    }

    node* ekle(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->sol = t->sag = NULL;
        }
        else if(x < t->data)
            t->sol = ekle(x, t->sol);
        else if(x > t->data)
            t->sag = ekle(x, t->sag);
        return t;
    }

    node* araMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->sol == NULL)
            return t;
        else
            return araMin(t->sol);
    }

    node* araMax(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->sag == NULL)
            return t;
        else
            return araMax(t->sag);
    }

    node* sil(int x, node* t)
    {
        node* temp;
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            t->sol = sil(x, t->sol);
        else if(x > t->data)
            t->sag = sil(x, t->sag);
        else if(t->sol && t->sag)
        {
            temp = araMin(t->sag);
            t->data = temp->data;
            t->sag = sil(t->data, t->sag);
        }
        else
        {
            temp = t;
            if(t->sol == NULL)
                t = t->sag;
            else if(t->sag == NULL)
                t = t->sol;
            delete temp;
        }

        return t;
    }

    void inorder(node* t)
    {
         if (t == NULL) return;

    // Create an empty queue for level order tarversal
    queue<node *> q;

    // Enqueue Root and initialize height
    q.push(t);

    while (q.empty() == false)
    {
        // nodeCount (queue size) indicates number
        // of nodes at current lelvel.
        int nodeCount = q.size();

        // Dequeue all nodes of current level and
        // Enqueue all nodes of next level
        while (nodeCount > 0)
        {
            node *node = q.front();
            cout << node->data << " ";
            q.pop();
            if (node->sol != NULL)
                q.push(node->sol);
            if (node->sag != NULL)
                q.push(node->sag);
            nodeCount--;
        }
        cout << endl;
    }
    }

    node* ara(node* t, int x)
    {
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            return ara(t->sol, x);
        else if(x > t->data)
            return ara(t->sag, x);
        else
            return t;
    }






public:
    agac()
    {
        root = NULL;
    }

    ~agac()
    {
        root = ilk(root);
    }

    void ekle(int x)
    {
        root = ekle(x, root);
    }

    void sil(int x)
    {
        root = sil(x, root);
    }

    void yazdir()
    {
        inorder(root);
        cout << endl;
    }

    void arama(int x)
    {
        root = ara(root, x);
    }

};

int main()
{
    agac* t=new agac();;
    t->ekle(20);
    t->ekle(25);
    t->ekle(15);
    t->ekle(10);
    t->ekle(30);
    t->yazdir();
    t->sil(20);
    t->yazdir();
    t->sil(25);
    t->yazdir();
    t->sil(30);
    t->yazdir();
    cout<<"\n--------------------\n";
}