//削除するノードを根とする左部分木の一番右か右部分木の一番左の二通りあると思うけど
//今回は前者を採用するみたい．

#include <iostream>
#include <stdio.h>
#define N_MAX 500000
using namespace std;
//thik&solve easy 

int n;//num of input

class node{//将来を見据えて動的にしています
public:
	int *key;
	node *parent;
	node *l_chld;
	node *r_chld;

	node(int n){
		key =new int(n);
		
		parent = NULL;
		l_chld = NULL;
		r_chld = NULL;
	}

	~node(){
		delete key;
		delete parent;
		delete l_chld;
		delete r_chld;
	}
};

void insert(node **root,node *z){
	node *y;
	node *x;
	y = NULL;
	x = *root;
	while(x != NULL){
		y = x;
		if(*(z->key) < *(x->key))
			x = x->l_chld;
		else
			x = x->r_chld;
		z->parent = y;
	}

	if(y == NULL)
		*root = z;
	else if(*(z->key) < *(y->key))
		y->l_chld = z;
	else
		y->r_chld = z;
	
}

void preorder(node* u){
	node* pos;
	cout <<" " <<*(u->key);

	if(u->l_chld != NULL){
		pos = u->l_chld;
		preorder(pos);
	}

	if(u->r_chld != NULL){
		pos = u->r_chld;
		preorder(pos);
	}
}

void inorder(node* u){
	node* pos;
	
	if(u->l_chld != NULL){
		pos = u->l_chld;
		inorder(pos);
	}
	cout <<" " <<*(u->key);

	if(u->r_chld != NULL){
		pos = u->r_chld;
		inorder(pos);
	}
}

void print(node *u){
	inorder(u);
	cout <<endl;

	preorder(u);
	cout <<endl;

}

bool find(node* u,int k){
	node* pos;
	bool b;
	if(k == *(u->key)) return true;

	if(k < *(u->key)){
		if(u->l_chld == NULL) return false;//一致するとすれば左の子だが左の子がいない
		pos = u->l_chld;
		b = find(pos,k);
	}else{
		if(u->r_chld == NULL) return false;//々右々
		pos = u->r_chld;
		b = find(pos,k);
	}
	return b;
}

node* search(node* u,int k){
	node* pos;
	node* b;
	if(k == *(u->key)) return u;

	if(k < *(u->key)){
		if(u->l_chld == NULL) return NULL;//一致するとすれば左の子だが左の子がいない
		pos = u->l_chld;
		b = search(pos,k);
	}else{
		if(u->r_chld == NULL) return NULL;//々右々
		pos = u->r_chld;
		b = search(pos,k);
	}
	return b;
}

void delete_node(node* u,int k){
	node* z;
	node* nd_tmp;
	node* y;
	z = search(u,k);

	if(z == NULL){
		cout <<"no such key" <<endl;
		return;
	}

	if(z->l_chld == NULL && z->r_chld == NULL){//zが子を持たない
		nd_tmp = z->parent;
		if(z == nd_tmp->l_chld) nd_tmp->l_chld =NULL;
		else nd_tmp->r_chld = NULL;
		//delete z;
	}
	else if(z->l_chld != NULL && z->r_chld != NULL){//zが二つ子を持つ
		y = z->r_chld;
		while(y->l_chld != NULL){
			y = y->l_chld;
		}

		z->key = y->key;

		nd_tmp = y->parent;
		if(y == nd_tmp->l_chld) nd_tmp->l_chld =NULL;
		else nd_tmp->r_chld = NULL;
		//delete y;
	}
	else{//zが子を一つだけ持つ
		if(z->l_chld != NULL){//zに左の子がいる
			(z->l_chld)->parent = z->parent;

			if(z == z->parent->l_chld) z->parent->l_chld = z->l_chld;
			else z->parent->r_chld = z->l_chld;

			//delete z;
		}
		else{//zに右の子がいる
			z->r_chld->parent = z->parent;

			if(z == z->parent->l_chld) z->parent->l_chld = z->r_chld;
			else z->parent->r_chld = z->r_chld;

			//delete z;
		}
	}
	return;//はじめこれ書き忘れて詰まってたんやで！信じられる？
}

int main(){
	char type[100];
	int z;
	node* root;
	root = NULL;

	node** rtroot = &root;

	scanf("%d",&n);
	
	for(int i=0;i<n;i++){
		scanf("%s",&type);
		if(type[0] == 'i'){
			scanf("%d",&z);

			//ポインタの作成(ちなみにndの寿命(=スコープ)はfor文の内部)
			node* nd;
			//新しく挿入するオブジェクトを作成し，ndの指す先に指定
			nd = new node(z);

			insert(rtroot,nd);
		}else if(type[0] == 'p'){
			print(root);
		}else if(type[0] == 'f'){
			scanf("%d",&z);

			if(find(root,z))cout <<"yes" <<endl;
			else cout <<"no" <<endl;
		}else if(type[0] == 'd'){
			scanf("%d",&z);

			delete_node(root,z);
		}else{
			cout <<"error type" <<endl;
		}
	}

	return 0;
}

Measured memory_bytes: 32468