#include <stdio.h>
using namespace std;

class BinaryTree
{
private:

	class Node
	{
	public:
		Node ()
		{
			this->parent = NULL;
			this->left = NULL;
			this->right = NULL;
		}

		int value;
		Node* parent;
		Node* left;
		Node* right;
	};

	Node* root;

	void PreOrder (Node* node)
	{
		if (node != NULL)
		{
			printf (" %d", node->value);
			PreOrder (node->left);
			PreOrder (node->right);
		}
	}
	void InOrder (Node* node)
	{
		if (node != NULL)
		{
			InOrder (node->left);
			printf (" %d", node->value);
			InOrder (node->right);
		}
	}
	void DeletePostOrder (Node* node)
	{
		if (node != NULL)
		{
			DeletePostOrder (node->left);
DeletePostOrder (node->right);
delete node;
		}
	}

	Node* GetMiniMum (Node* node)
	{
		while (node->left != NULL)
		{
			node = node->left;
		}

		return node;
	}
	Node* GetSuccessor (Node* node)
	{
		if (node->right != NULL)
		{
			return GetMiniMum (node->right);
		}

		Node* parent = node->parent;

		while (parent != NULL&&node == parent->right)
		{
			node = parent;
			parent = parent->parent;
		}

		return parent;
	}

public:
	BinaryTree ()
	{
		root = NULL;
	}
	~BinaryTree ()
	{
		DeletePostOrder (root);
	}

	void Insert (int value)
	{
		Node* searchNode = root;
		Node* parentNode = NULL;

		while (searchNode != NULL)
		{
			parentNode = searchNode;

			if (value < searchNode->value)
			{
				searchNode = searchNode->left;
			}
			else
			{
				searchNode = searchNode->right;
			}
		}

		Node* newNode = new Node;
		newNode->value = value;
		newNode->parent = parentNode;

		if (parentNode == NULL)
		{
			root = newNode;
		}
		else
		{
			if (value < parentNode->value)
			{
				parentNode->left = newNode;
			}
			else
			{
				parentNode->right = newNode;
			}
		}
	}

	bool Find (int value)
	{
		Node* searchNode = root;

		while (searchNode != NULL)
		{
			if (searchNode->value == value)
			{
				return true;
			}
			else if (value < searchNode->value)
			{
				searchNode = searchNode->left;
			}
			else
			{
				searchNode = searchNode->right;
			}
		}

		return false;
	}

	void Delete (int value)
	{
		Node* searchNode = root;

		while (searchNode != NULL)
		{
			if (value == searchNode->value)
			{
				break;
			}
			else if (value < searchNode->value)
			{
				searchNode = searchNode->left;
			}
			else
			{
				searchNode = searchNode->right;
			}
		}

		//?????????????????´???
		if (searchNode->left == NULL&&searchNode->right == NULL)
		{
			Node* parent = searchNode->parent;

			if (parent->left == searchNode)
			{
				parent->left = NULL;
			}
			else
			{
				parent->right = NULL;
			}

			delete searchNode;
		}
		//??????2????????´???
		else if (searchNode->left != NULL&&searchNode->right != NULL)
		{
			//1.????????????????????????????¬????????????¢???
			Node* deleteNode = GetSuccessor (searchNode);

			//2.??????????????????????????????????±???????
			Node* childNode = NULL;

			if (deleteNode->left != NULL)
			{
				childNode = deleteNode->left;
			}
			else
			{
				childNode = deleteNode->right;
			}

			//3.?????????????????????????¨??????????
			if (childNode != NULL)
			{
				childNode->parent = deleteNode->parent;
			}

			//4.?¬???????????????¨????????????????????????
			if (deleteNode->parent == NULL)
			{
				root = childNode;
			}
			//???????????????????´???§????????°
			else if (deleteNode == deleteNode->parent->left)
			{
				deleteNode->parent->left = childNode;
			}
			//???????????????????´???§????????°
			else
			{
				deleteNode->parent->right = childNode;
			}
			
			//5.z?????????y??????????????????
			if (deleteNode != searchNode)
			{
				searchNode->value = deleteNode->value;
			}

			//6.y???????????????
			delete deleteNode;
		}
		//??????1????????´???
		else if (searchNode->left != NULL)
		{
			Node* parent = searchNode->parent;
			Node* child = searchNode->left;

			if (parent->left == searchNode)
			{
				parent->left = child;
			}
			else
			{
				parent->right = child;
			}

			child->parent = parent;

			delete searchNode;
		}
		else
		{
			Node* parent = searchNode->parent;
			Node* child = searchNode->right;

			if (parent->left==searchNode)
			{
				parent->left = child;
			}
			else
			{
				parent->right = child;
			}

			child->parent = parent;

			delete searchNode;
		}
	}

	void Print ()
	{
		InOrder (root);
		printf ("\n");
		PreOrder (root);
		printf ("\n");
	}
};

int main ()
{
	int dataCount;
	scanf ("%d", &dataCount);

	BinaryTree binaryTree;

	for (int lp = 0; lp < dataCount; lp++)
	{
		char inputStr[10];
		scanf ("%s", inputStr);

		char item = inputStr[0];

		if (item == 'i')
		{
			int num;	
			scanf ("%d", &num);
			binaryTree.Insert (num);
		}
		else if (item == 'f')
		{
			int num;	
			scanf ("%d", &num);

			bool isFind = binaryTree.Find (num);

			if (isFind)
				printf ("yes\n");
			else
				printf ("no\n");
		}
		else if (item == 'd')
		{
			int num;
			scanf ("%d", &num);
			binaryTree.Delete (num);
		}
		else
		{
			binaryTree.Print ();
		}
	}

	return 0;
}

Measured memory_bytes: 21424