//============================================================================
// Name        : BinarySearchTree.cpp
// Author      : Ken
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <map>
using namespace std;

class Node{
public:
	int id;
	Node* p_parent;
	Node* p_left_child;
	Node* p_right_child;

	Node(): id(-1), p_parent(NULL), p_left_child(NULL), p_right_child(NULL){};
	Node(const int n):id(n), p_parent(NULL), p_left_child(NULL), p_right_child(NULL){}
};

class BinarySearchTree{
public:
	map<int, Node> node_map;
	int root_id;

	BinarySearchTree(): node_map(), root_id(){};


	void insert(int input){
		node_map[input] = Node(input); // THIS IS **PASS-BY-VALUE** !!!
		Node* y = NULL; //parent of x


		if(node_map.size()>=2){
		    Node* x = &node_map[root_id];
		    //cout << "x->id: " << x->id << "\n";

	    	while(x != NULL){
	    		y = x;

		    	if(node_map[input].id < x->id){
			    	x = x->p_left_child; // move to the left child
	    		}else{
		    		x = x->p_right_child; // move to the right child
		    	}
		    }
	    	//cout << "end of while loop\n";

	    	//if(x != NULL){
	    	//    cout << "x->id: " << x->id;}

	    	//if(y != NULL){
			//    cout << ", y->id: " << y->id;}

			//cout << ", z->id: " << node_map[z.id].id;

			//cout << "\n";

			node_map[input].p_parent = y;
		}

		if(y == NULL){ // T is empty
			root_id = node_map[input].id;
		}else if(input < y->id){
			y->p_left_child = &node_map[input];
		}else{
			y->p_right_child = &node_map[input];
		}
	}

	void printInorder(int node_id){
		Node& p_node = node_map[node_id];

		if(p_node.p_left_child != NULL){
			//cout << "print left branch\n";
		    printInorder(p_node.p_left_child->id);
		}

		cout << " " << node_id;

		if(p_node.p_right_child != NULL){
			//cout << "print right branch\n";
			printInorder(p_node.p_right_child->id);
		}
	}

	void printInorderTree(){
		printInorder(root_id);
	}

	void printPreorder(int node_id){
		Node& p_node = node_map[node_id];
		cout << " " << node_id;

		if(p_node.p_left_child != NULL){
		    printPreorder(p_node.p_left_child->id);
		}

		if(p_node.p_right_child != NULL){
			printPreorder(p_node.p_right_child->id);
		}
	}

	void printPreorderTree(){
		printPreorder(root_id);
	}

	void writeMap(){
		cout << "root id: " << root_id << ", root node: " << node_map[root_id].id << "\n";

		map<int, Node>::iterator p;
		for(p = node_map.begin(); p != node_map.end(); p++){
			cout << p->first << " " << p->second.id << "\n";
			Node& p_node = p->second;
			if(p_node.p_parent != NULL){
				cout << " parent: " << p_node.p_parent->id;
			}
			if(p_node.p_left_child != NULL){
				cout << " left_child: " << p_node.p_left_child->id;
			}
			if(p_node.p_right_child != NULL){
				cout << " right_child: " << p_node.p_right_child->id;
			}
			cout << "\n";
		}
	}

	bool find(int input){
		bool isFound = false;
		Node* x = &node_map[root_id];
		while(x != NULL){
			if(x->id == input){
				isFound = true;
				break;
			}else if(x->id > input){
				x = x->p_left_child;
			}else{
				x = x->p_right_child;
			}
		}

		return isFound;
	}

	void delete_node(int input){
		Node& z = node_map[input];
		if(z.p_left_child == NULL and z.p_right_child == NULL){
			if(z.p_parent->id < z.id){ // z is right child of z's parent
				z.p_parent->p_right_child = NULL;
			}else{ // z is left child of z's parent
				z.p_parent->p_left_child = NULL;
			}
			node_map.erase(input);
		}else if(z.p_left_child != NULL and z.p_right_child == NULL){
			z.p_left_child->p_parent = z.p_parent;
			if(z.p_parent->id < z.id){ // z is right child of z's parent
				z.p_parent->p_right_child = z.p_left_child;
			}else{
				z.p_parent->p_left_child = z.p_left_child;
			}
			node_map.erase(input);
		}else if(z.p_left_child == NULL and z.p_right_child != NULL){
			z.p_right_child->p_parent = z.p_parent;
			if(z.p_parent->id < z.id){ // z is right child of z's parent
				z.p_parent->p_right_child = z.p_right_child;
			}else{
				z.p_parent->p_left_child = z.p_right_child;
			}
			node_map.erase(input);
		}else{ // z has left and right child
			Node* x = z.p_right_child;
			Node* y = NULL; //x's parent
			while(x != NULL){
				y = x;
				x = x->p_left_child;
			}
			int old_z_id = z.id;


			if(y->p_left_child == NULL and y->p_right_child == NULL){
				if(y->id == y->p_parent->p_left_child->id){
				    y->p_parent->p_left_child = NULL;
				}else if(y->id == y->p_parent->p_right_child->id){
					y->p_parent->p_right_child = NULL;
				}

			}else if(y->p_left_child == NULL and y->p_right_child != NULL){
				y->p_right_child->p_parent = y->p_parent;
				y->p_parent->p_left_child = y->p_right_child;
			}

			z.id = y->id;
			node_map[y->id] = z;

			node_map.erase(old_z_id);
		}
	}
};


int main() {
	BinarySearchTree tree;

	int n, input;
	string command;
	cin >> n;

	for(int i=0; i<n; i++){
		cin >> command;
		if(command == "insert"){
			cin >> input;
			//cout << "insert(" << input << ")\n";
			tree.insert(input);
			//tree.writeMap();
			//cout << "\n\n\n";
		}
		if(command == "print"){
			//cout << "printInorderTree()\n";
			tree.printInorderTree();
			cout << "\n";
			//cout << "printPreorderTree()\n";
			tree.printPreorderTree();
			cout << "\n";
		}
		if(command == "find"){
			cin >> input;
			bool isFound = tree.find(input);
			if(isFound){
				cout << "yes\n";
			}else{
				cout << "no\n";
			}
		}
		if(command == "delete"){
			cin >> input;
			tree.delete_node(input);
			//cout << "delete: " << input << "\n";
			//tree.writeMap();
		}
	}

	return 0;
}



Measured memory_bytes: 34416