#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

struct node{
	int data;
	node *l, *r;
};

node *new_node(int in){
	node *ret = new node;
	ret->data = in;
	ret->l = NULL;
	ret->r = NULL;
	return ret;
}

void insert_node(node **root, int in){
	node *add = new_node(in);
	if(*root == NULL){
		*root = add;
		return ;
	}
	node *p = *root, *pp = NULL;
	while(p != NULL){
		pp = p;
		if(add->data < p->data) p = p->l;
		else p = p->r;
	}
	if(add->data < pp->data) pp->l = add;
	else pp->r = add;
	return ;
}

void print_n(node *root, bool mode){
	if(mode == true) cout << " " << root->data;
	if(root->l != NULL) print_n(root->l, mode);
	if(mode == false) cout << " " << root->data;
	if(root->r != NULL) print_n(root->r, mode);
}

void print_node(node *root){
	print_n(root, false);
	cout << endl;
	print_n(root, true);
	cout << endl;
}

void find_node(node *root, int in){
	bool ans = false;
	while(root != NULL){
		if(in == root->data){
			ans = true;
			break;
		}else if(in < root->data){
			root = root->l;
		}else{
			root = root->r;
		}
	}
	if(ans == false) cout << "no" << endl;
	else cout << "yes" << endl;
}

void delete_node(node **root, int in){
	node *p = *root, *pp = NULL;
	while(p != NULL){
		if(p->data == in) break;
		pp = p;
		if(in < p->data) p = p->l;
		else p = p->r;
	}
	if(p->l == NULL && p->r == NULL){
		if(in < pp->data) pp->l = NULL;
		else pp->r = NULL;
		delete p;
		return ;
	}
	if(p->l == NULL){
		if(in < pp->data) pp->l = p->r;
		else pp->r = p->r;
		delete p;
		return;
	}
	if(p->r == NULL){
		if(in < pp->data) pp->l = p->l;
		else pp->r = p->l;
		delete p;
		return;
	}
	node *rl = p->r, *prl = p;
	while(rl->l != NULL){
		prl = rl;
		rl = rl->l;
	}
	if(in < pp->data) pp->l = rl;
	else pp->r = rl;
	if(prl != p)prl->l = rl->r;
	else prl->r = rl->r;
	rl->l = p->l;
	rl->r = p->r;
	delete p;
}

int main(){
	int n;
	cin >> n;
	node *root = NULL;
	rep(i, n){
		string s;
		cin >> s;
		if(s == "print"){
			print_node(root);
		}else if(s == "find"){
			int in;
			cin >> in;
			find_node(root, in);
		}else if(s == "delete"){
			int in;
			cin >> in;
			delete_node(&root, in);
		}else{
			int in;
			cin >> in;
			insert_node(&root, in);
		}
	}
	return 0;
}

#include <iostream>
#include <bits/stdc++.h>
#define MAX_SIZE 500010
#define INFTY 2000000000
using namespace std;

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k) {
    Node *z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    Node *y = NIL;
    Node *x = root;
    while (x != NIL) {
        y = x;
        if (z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;
    if (y == NIL) root = z;
    else if (z->key < y->key) y->left = z;
    else y->right = z;
}

Node *find(int k) {
    Node *x = root;
    while (x != NIL && k != x->key) {
        if (k < x->key) x = x->left;
        else x = x->right;
    }
    return x;
}

void replace(Node *x, Node *y, Node *z) {

}

Node *getMInimum(Node *x) {
    while (x->left != NIL) x = x->left;
    return x;
}

Node *getSuccessor(Node *x) {
    if (x->right != NIL) return getMInimum(x->right);
    Node *y = x->parent;
    while (y != NIL && x == y->right) {
        x = y;
        y = x->parent;
    }
    return y;
}

void deleteNode(Node *z) {
    Node *x, *y;
    if (z->left != NIL && z->right != NIL) y = getSuccessor(z);
    else y = z;
    if (y->left != NIL) x  = y->left;
    else x = y->right;

    if (x != NIL) x->parent = y->parent;

    if (y->parent == NIL) root = x;
    else if (y->parent->left == y) y->parent->left = x;
    else y->parent->right = x;
    if (y != z) z->key = y->key;
    free(y);
}



void findPrint(int k) {
    if (find(k) == NIL) printf("no\n");
    else printf("yes\n");
}

void preorder(Node* u) {
    if (u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

void inorder(Node* u) {
    if (u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);    
}

void postorder(Node* u) {
    if (u == NIL) return;
    postorder(u->left);
    postorder(u->right);
    printf(" %d", u->key);
}

void print() {
    inorder(root);
    printf("\n");
    preorder(root);
    printf("\n");
}

int main(){
    int n, k;
    char cmd[10];
    root = NIL;
    cin >> n;
    for (int i=0; i < n; i++) {
        scanf("%s%d\n", cmd, &k);
        // cout << cmd << k << endl;
        if (cmd[0] == 'i') insert(k);
        else if (cmd[0] == 'f') findPrint(k);
        else if (cmd[0] == 'd') deleteNode(find(k));
        else if (cmd[0] == 'p') print();
    }
    return 0;
} 
