#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

struct Node{
    int key;
    Node* left;
    Node* right;
    Node* par;
};

struct binarySearchTree{
    Node* root;
    
    binarySearchTree(){
        root=NULL;
    }
    
    void insert(int key);
    void inorderTreeWalk(Node* node);
    void preorderTreeWalk(Node* node);
    bool find(Node* node,int key);
    void freeNode(Node* node);
	void deleteNode(Node* node,int key);
};

void binarySearchTree::insert(int key){
    Node* z=(Node*)malloc(sizeof(Node));
    z->key=key;
    z->left=z->right=z->par=NULL;
    
    if(root==NULL){
        root=z;
        return;
    }

    Node* y=NULL;
    Node*x=root;
    
    while(x!=NULL){
        y=x;
        if(x->key>key){
            x=x->left;
        }
        else{
            x=x->right;
        }
    }
    
    z->par=y;
    if(y->key>key){
        y->left=z;
    }
    else{
        y->right=z;
    }
    return;
}

void binarySearchTree::inorderTreeWalk(Node* node){
    if(node!=NULL){
        inorderTreeWalk(node->left);
        cout<<" "<<node->key;
        inorderTreeWalk(node->right);
    }
    return;
}

void binarySearchTree::preorderTreeWalk(Node* node){
    if(node!=NULL){
        cout<<" "<<node->key;
        preorderTreeWalk(node->left);
        preorderTreeWalk(node->right);
    }
    return;
}

bool binarySearchTree::find(Node* node,int key){
    if(node==NULL){
        return 0;
    }
    else if(node->key==key){
        return 1;
    }
    else if(node->key>key){
        return find(node->left,key);
    }
    else{
        return find(node->right,key);
    }
}

void binarySearchTree::freeNode(Node* node){
    if(node->left==NULL){
        if(node->right==NULL){
            if(node->par->key<node->key){
                node->par->right=NULL;
                free(node);
            }
            else{
                node->par->left=NULL;
                free(node);
            }
        }
        else{
            if(node->par->key<node->key){
                node->right->par=node->par;
                node->par->right=node->right;
                free(node);
            }
            else{
                node->right->par=node->par;
                node->par->left=node->right;
                free(node);
            }
        }
    }
    else if(node->right==NULL){
        if(node->par->key<node->key){
            node->left->par=node->par;
            node->par->right=node->left;
            free(node);
        }
        else{
            node->left->par=node->par;
            node->par->left=node->left;
            free(node);
        }
    }
    else{
        if(node->right->left==NULL){
            node->key=node->right->key;
            free(node->right);
            node->right=NULL;
        }
        else{
            Node* tmp=node->right->left;
            while(tmp->left!=NULL){
                tmp=tmp->left;
            }
            if(tmp->right==NULL){
                node->key=tmp->key;
                tmp->par->left=NULL;
                free(tmp);
            }
            else{
                node->key=tmp->key;
                tmp->key=tmp->right->key;
                free(tmp->right);
                tmp->right=NULL;
            }
        }
    }
    return;
}

void binarySearchTree::deleteNode(Node* node,int key){
    if(node==NULL){
        return;
    }
    else if(node->key==key){
        freeNode(node);
    }
    else if(node->key>key){
        return deleteNode(node->left,key);
    }
    else{
        return deleteNode(node->right,key);
    }
}

int main(void){
    int n,x,i;
    string s;
    binarySearchTree tree;

    cin>>n;
    
    for(i=0;i<n;i++){
        cin>>s;
        if(s[0]=='i'){
            cin>>x;
            tree.insert(x);
        }
        else if(s[0]=='p'){
            tree.inorderTreeWalk(tree.root);
            cout<<endl;
            tree.preorderTreeWalk(tree.root);
            cout<<endl;
        }
        else if(s[0]=='f'){
            cin>>x;
            if(tree.find(tree.root,x)){
                cout<<"yes"<<endl;
            }
            else{
                cout<<"no"<<endl;
            }
        }
				else{
					cin>>x;
					tree.deleteNode(tree.root,x);
				}
    }
    return 0;
}


Measured memory_bytes: 21956