#include <stdio.h>
#include <iostream>
using namespace std;

class Node {
private:
	int id;
	Node *parent;
	Node *child_l;
	Node *child_r;
public:
	Node(int id){ this->id = id; parent = NULL; child_l = NULL; child_r = NULL;}
	void setId(int id){ this->id = id; }
	void setChildl(Node *nl);
	void setChildr(Node *nr);
	void setParent(Node *np){ parent = np; }
	int getId(){ return id; }
	Node *getParent(){ return parent; }
	Node *getChildl(){ return child_l; }
	Node *getChildr(){ return child_r; }
	Node *searchLeft();
};

void Node::setChildl(Node *nl)
{
	child_l = nl;
	if (child_l != NULL) child_l->setParent(this);
}

void Node::setChildr(Node *nr)
{
	child_r = nr;
	if (child_r != NULL) child_r->setParent(this);
}

Node *Node::searchLeft()
{
	if (child_l == NULL) return this;
	return child_l->searchLeft();
}

class BinaryTree {
private:
	Node *root;
	void del0(Node *node, char parent_rl);
	void del1(Node *node, char parent_rl, char child_rl);
	void del2(Node *node);
	void walkPreorder(Node *node);
	void walkInorder(Node *node);
public:
	BinaryTree(){ root = NULL; }
	void insert(int id);
	void find(int id);
	void del(int id);
	void walkPreorder();
	void walkInorder();
};

void BinaryTree::insert(int id)
{
	if (root == NULL) {
		root = new Node(id);
		return;
	}

	Node *node = root;
	while (1) {
		if (id < node->getId()) {
			if (node->getChildl() == NULL) {
				node->setChildl(new Node(id));
				break;
			}
			else {
				node = node->getChildl();
			}
		}
		else if (id > node->getId()) {
			if (node->getChildr() == NULL) {
				node->setChildr(new Node(id));
				break;
			}
			else {
				node = node->getChildr();
			}
		}
	}
}

void BinaryTree::find(int id)
{
	Node *node = root;
	while (node != NULL) {
		if (id == node->getId()) {
			cout << "yes" << endl;
			return;
		}
		else if (id < node->getId()) {
			node = node->getChildl();
		}
		else {
			node = node->getChildr();
		}
	}
	cout << "no" <<endl;
}

void BinaryTree::del0(Node *node, char parent_rl)
{
	Node *np = node->getParent();
	if (parent_rl == 'l') np->setChildl(NULL);
	else if (parent_rl == 'r') np->setChildr(NULL);
	else root = NULL;
	delete node;
}

void BinaryTree::del1(Node *node, char parent_rl, char child_rl)
{
	Node *np = node->getParent();
	Node *nc;
	if (child_rl == 'l') nc = node->getChildl();
	else nc = node->getChildr();
	if (parent_rl == 'l') np->setChildl(nc);
	else if (parent_rl == 'r') np->setChildr(nc);
	else root = nc;
	delete node;
}

void BinaryTree::del2(Node *node)
{
	char parent_rl = 'l';
	Node *ny = (node->getChildr())->searchLeft();
	node->setId(ny->getId());
	if ((node->getChildr())->getId() == ny->getId()) parent_rl = 'r';
	if (ny->getChildr() == NULL) del0(ny, parent_rl);
	else del1(ny, parent_rl, 'r');
}

void BinaryTree::del(int id)
{
	Node *node = root;
	char parent_rl = '\0';
	while (node != NULL) {
		if (id == node->getId()) break;
		else if (id < node->getId()) {
			node = node->getChildl();
			parent_rl = 'l';
		}
		else {
			node = node->getChildr();
			parent_rl = 'r';
		}
	}
	if (node == NULL) return;

	if (node->getChildl() == NULL && node->getChildr() == NULL) del0(node, parent_rl);
	else if (node->getChildl() != NULL && node->getChildr() != NULL) del2(node);
	else if (node->getChildl() != NULL) del1(node, parent_rl, 'l');
	else del1(node, parent_rl, 'r');
	return;
}

void BinaryTree::walkPreorder()
{
	walkPreorder(root);
	cout << endl;
}

void BinaryTree::walkPreorder(Node *node)
{
	if (node == NULL) return;
	cout << " " << node->getId();
	walkPreorder(node->getChildl());
	walkPreorder(node->getChildr());
}

void BinaryTree::walkInorder()
{
	walkInorder(root);
	cout << endl;
}

void BinaryTree::walkInorder(Node *node)
{
	if (node == NULL) return;
	walkInorder(node->getChildl());
	cout << " " << node->getId();
	walkInorder(node->getChildr());
}

int main(void)
{
	BinaryTree bt;

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		char command[7] = "\0";
		cin >> command;
		if (command[0] == 'i') {			
			int id;
			cin >> id;
			bt.insert(id);
		}
		else if (command[0] == 'f') {
			int id;
			cin >> id;
			bt.find(id);
		}
		else if (command[0] == 'd') {
			int id;
			cin >> id;
			bt.del(id);
		}
		else {
			bt.walkInorder();
			bt.walkPreorder();
		}
	}
		
	return 0;
}

Measured memory_bytes: 21816