#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

class BinNode
{
public:
    int data;
    BinNode* parent,*left_child,*right_child;
    BinNode(int d=-1,BinNode* p=NULL,BinNode* l=NULL,BinNode* r=NULL):data(d),parent(p),left_child(l),right_child(r){}
    BinNode* insertAsLc(int u)
    {
        return left_child=new BinNode(u,this);
    }
    BinNode* insertAsRc(int u)
    {
        return right_child=new BinNode(u,this);
    }
    BinNode* succ() //?????????????????´??\?????§
    {
        if(right_child) //??????????????????
        {
            BinNode* u=right_child;
            while(u->left_child)
            {
                u=u->left_child; //????????????????????±??\
            }
            return u;
        }
        else //????????????????????????????????°?????????????????????????????????????\????
        {
            BinNode* u=this;
            BinNode* p=u->parent;
            while(u!=p->right_child)
            {
                u=p;
                p=p->parent;
            }
            return p; //????????\???????\????
        }
    }
};
void printNode(BinNode* u)
{
    cout<<" "<<u->data;
}
class BST
{
    BinNode* _root;
    BinNode* _hot;
public:
    BST() {_root=_hot=NULL;}
    bool remove(BinNode* u);
    BinNode* search(int u);
    BinNode* searchIn(BinNode* p,int u,BinNode*& hot);
    BinNode* insert(int u);
    bool del(int u);
    void visitLeftbranch(BinNode* u,stack<BinNode*>& S);
    void print_preOrder(); //??????????????????
    void print_inOrder(); //??????????????????
};
BinNode* BST::searchIn(BinNode* p,int u,BinNode*& hot)
{
    if(p==NULL) return NULL; //?????????
    hot=p; //?????°_hot??????
    if(p->data==u) return p;
    return searchIn((u<p->data?p->left_child:p->right_child),u,hot); //???????????°
}

BinNode* BST::search(int u)
{
    BinNode* hot=NULL;
    BinNode* t=searchIn(_root,u,hot);
    if(t) return t;
    return hot; //??????????????¨??\??????????????????????????????????????????
}

BinNode* BST::insert(int u)
{
    if(!_root) return _root=new BinNode(u); //???????°±?????\???????????????
    BinNode* t=search(u);
    if(t->data==u) return t; //????????????????????????????????¨
    return (u<t->data?t->insertAsLc(u):t->insertAsRc(u)); //?????°?????\
}
bool BST::remove(BinNode *u) //u?????????????????¶???
{
    if(u)
    {
        //???????????¶????????????
        u == u->parent->left_child ? (u->parent->left_child = NULL) : (u->parent->right_child = NULL);
        u->parent = NULL;
        delete u;
        return true;
    }
    return false;
}
bool BST::del(int x)
{
    BinNode* u=search(x);
    BinNode* w=u;
    BinNode* succ=NULL; //???????????????????????\??????
    if(u->data!=x) return false; //????????????????????¨

    //????????¨?????????????????????
    if(!u->left_child) //?????????????????¨????????????
    {
        succ=u->right_child;
    }
    if(!u->right_child) //?????????????????¨????????????
    {
        succ=u->left_child;
    }
    else //??????????????????
    {
        w=w->succ(); //?????°??´??\?????§
        swap(w->data,u->data); //?????¢???????????°???
        BinNode* p=w->parent; //???????????????????????¶???
        ((u==p)?(p->right_child):(p->left_child))=succ=w->right_child;
    }
    //?§£?????\????????????????????§
    _hot=w->parent; //??°??????????¢??????????????????¶???
    if(succ) //????????\?????????????????????
        succ->parent=_hot; //??£?°±????????§
    if(w) delete w;
    return true;
}
void BST::visitLeftbranch(BinNode *u, stack<BinNode*> &S)
{
    while(u)
    {
        printNode(u); //?????????
        S.push(u->right_child); //???????????\???
        u=u->left_child;
    }
}
void BST::print_preOrder()
{
    BinNode* u=_root;
    stack<BinNode*> S;
    while(true)
    {
        visitLeftbranch(u,S);
        if(!S.empty()) {u=S.top();S.pop();}
        else break;
    }
}
void BST::print_inOrder()
{
    stack<BinNode*> S;
    BinNode* u=_root;
    while(true)
    {
        if(u)
        {
            S.push(u);
            u=u->left_child;
        }
        else if(!S.empty())
        {
            u=S.top();S.pop(); //???????????¶
            printNode(u);
            u=u->right_child; //??¬??\?????????
        }
        else break;
    }
}
int main()
{
    BST Tree;
    int order_num;
    char order[10];
    int target_num;
    cin>>order_num;
    for(int i=0;i<order_num;i++)
    {
        cin>>order;
        switch(order[0])
        {
            case 'i': cin>>target_num; Tree.insert(target_num);break;
            case 'p': Tree.print_inOrder();cout<<endl;
                      Tree.print_preOrder();cout<<endl;
                      break;
            case 'f': cin>>target_num;
                if(Tree.search(target_num)->data==target_num) cout<<"yes"<<endl;
                else cout<<"no"<<endl;
                break;
            case 'd': cin>>target_num;Tree.del(target_num);
                break;
        }
    }
}

Measured memory_bytes: 21808