#include <iostream>
#include <fstream>
using namespace std;
struct item
    {
        int i;
        item* father;
        item* lson;
        item* rson;
        item() {lson=rson=NULL;}
    };
class derevo
{
private:    
    item* root;    
public:
    derevo();    
    bool find(int, item* &);
    bool findy(int, int&);
    bool insert(int);
    void prosh();
    void prosmotr(item* &, void vizit(item* &));
    void erasef(item* &);
    bool erase(int);
};
derevo::derevo()
{
    root=NULL;
}
bool derevo::find(int m,item* &yuo)
{
    if(root==NULL)
    {
        yuo=NULL;
        return false;
    }
    yuo=root;
    while(1)
    {
        if(yuo->i==m)
            return true;
        if(yuo->i>m)
        {
            if(yuo->lson==NULL)
                return false;
            yuo=yuo->lson;
        }
        else
        {
            if(yuo->rson==NULL)
                return false;
            yuo=yuo->rson;
        }
    }
}
bool derevo::findy(int m,int &i)
{
    if(root==NULL)
    {        
        return false;
    }
    item* yuo=root;
    while(1)
    {
        if(yuo->i==m)
        {
            i++;
            return true;
        }
        if(yuo->i>m)
        {
            i++;
            if(yuo->lson==NULL)
                return false;
            yuo=yuo->lson;
        }
        else
        {
            i++;
            if(yuo->rson==NULL)
                return false;
            yuo=yuo->rson;
        }
    }
}
bool derevo::insert(int p)
{
    item *q, *r;
    if((find(p,r))==true)
        return false;
    q=new item;
    q->i=p;
    if(r==NULL)
    {
        root=q;
        q->father=NULL;
    }
    else
    {
        q->father=r;
        if(r->i<p)
            r->rson=q;
        else
            r->lson=q;
    }
    return true;
}
void vizit(item* &p)
{
    cout << p->i << " ";
}
void derevo::prosh()
{
    prosmotr(root,vizit);
}
void derevo::prosmotr(item* &mhj, void vizit(item* &mhj))
{
    if(mhj!=NULL)
    {
        prosmotr(mhj->lson,vizit);
        vizit(mhj);
        prosmotr(mhj->rson,vizit);
    }
}
void derevo::erasef(item* &c)
{
    item* m;
    if(c->lson!=NULL)
        m=c->lson;
    else
        m=c->rson;
    if(m!=NULL)
        m->father=c->father;
    if(c->father==NULL)
        root=m;
    else
    {
        if((c->father)->lson==c)
            (c->father)->lson=m;
        else
            (c->father)->rson=m;
    }
    delete c;
    c=NULL;
}
bool derevo::erase(int inf)
{
    item *q, *r;
    if((find(inf,r))==false)
        return false;
    if((r->lson!=NULL)&&(r->rson!=NULL))
    {
        q=r->rson;
        while(q->lson!=NULL)
            q=q->lson;
        r->i=q->i;
        erasef(q);
    }
    else
        erasef®;
    return true;
}
int main()
{
    freopen("D:\\pushy.txt", "w", stdout);
    ifstream fin("D:\\push.txt");
    derevo j;
    char ind;
    while(fin>>ind)
    {
        int u,i=0;
        if((ind=='I')||(ind=='D')||(ind=='F'))
            fin>>u;
        switch(ind)
        {
        case 'I': j.insert(u); break;
        case 'D': j.erase(u); break;
        case 'F': j.findy(u,i); break;
        case 'L': j.prosh(); break;
        }        
    }    
}