// 二分探索木の削除
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

#define MAX_N 30
//const int NIL = -1;

typedef struct node
{
    // 節点の値
    int key;
    // 節点の親
    struct node *parent;
    // 節点の左の子
    struct node *left;
    // 節点の右の子
    struct node *right;
}Node;

// グローバル変数の定義
Node *p_Tree;

void preorderTreeWalk(Node *Tree);
void inorderTreeWalk(Node *Tree);
void postorderTreeWalk(Node *Tree);

void insert(int num);
bool deleteTree(int num);
bool find(Node *Tree, int num);

int main(void)
{

    int n, num;
    char str[10];

    cin >> n;

    for(int i = 0; i < n; i++)
    {
    	// 命令を取得
        scanf("%s", str);

        if( str[0] == 'i' )
        {
        	// --- 挿入の命令の時 ---

        	scanf("%d", &num);

            insert(num);
        }
        else if( str[0] == 'f' )
        {
            // --- 検索の命令の時 ---

        	scanf("%d", &num);

            if( find(p_Tree, num) )
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
        else if( str[0] == 'd' )
        {
            // --- 削除の命令の時 ---

        	scanf("%d", &num);
            deleteTree(num);
        }
        else
        {
        	// --- 表示の命令 ---

            inorderTreeWalk(p_Tree);
            printf("\n");
            preorderTreeWalk(p_Tree);
            printf("\n");
        }
    }

    return 0;
}

// ----------▼▼▼▼▼ 2分探索木の操作関数　▼▼▼▼▼----------

// 二分探索木の検索関数
bool find(Node *Tree, int num)
{
    bool ret = false;
    Node *tree = Tree;

    while( tree != NULL )
    {
        if( num < tree->key )
        {
            // 左の子を探索
            tree = tree->left;
        }
        else if( num > tree->key )
        {
            // 右の子を探索
            tree = tree->right;
        }
        else
        {
            // 値が見つかったので, 処理終了
            ret = true;
            break;
        }
    }

    return ret;
}

// 二分探索木の挿入関数
void insert(int num)
{
    Node *tree, *parent;

    // 追加する要素の親
    parent = NULL;
    // 木の根 ( 先頭アドレス )
    tree = p_Tree;

    Node *newNode = new Node;

    newNode->key = num;
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;

    while( tree != NULL )
    {
        // 親の候補の取得
    	parent = tree;

        if( newNode->key < tree->key )
        {
            // 左の子へ移動
        	tree = tree->left;
        }
        else
        {
            // 右の子へ移動
        	tree = tree->right;
        }
    }

    // 追加する要素の親を設定
    newNode->parent = parent;

    if( parent == NULL )
    {
        // 木が空の時
    	newNode->parent = NULL;
        // 木が空のなので, 実体を入れる
        p_Tree = newNode;

    }
    else if( newNode->key < parent->key )
    {
        // 左の子にする
    	parent->left = newNode;
    }
    else
    {
        // 右の子にする
    	parent->right = newNode;
    }

    return;
}

// 2分探索木の削除関数
bool deleteTree(int num)
{
    bool ret = true;
    Node *tree;

    // 木の根 ( 先頭アドレス )
    tree = p_Tree;

    while( tree != NULL && tree->key != num )
    {
        if( num < tree->key )
        {
            // 左の子へ移動
        	tree = tree->left;
        }
        else if( num > tree->key )
        {
            // 右の子へ移動
        	tree = tree->right;
        }
    }

    if( tree == NULL )
    {
        // 削除要素が無かった時
        ret = false;
    }
    else
    {
        // ----- 削除要素があった時 -----

        if( tree->left == NULL && tree->right == NULL )
        {
            // 削除要素が子を持たない時

            if( tree->key < tree->parent->key )
            {
                // 削除要素が自分の親の左の子の時
                tree->parent->left = NULL;
            }
            else
            {
                // 削除要素が自分の親の右の子の時
                tree->parent->right = NULL;
            }

            // 直接要素を削除する
            delete tree;
        }
        else if( tree->left != NULL && tree->right != NULL )
        {
            // 削除要素が子を2つ持つ時

            // ---▼▼▼ 削除する要素の右の子から値が最小の要素を検索する ▼▼▼---

            Node *minElement = tree->right;

            while( minElement->left != NULL )
            {
                minElement = minElement->left;
            }

            // ---▲▲▲ 削除する要素の右の子から値が最小の要素を検索する ▲▲▲---

            // ----- 置き換える要素に, データを設定する -----

            //if( minElement->right != NULL )
            //{
                // 置き換える要素の右の子を置き換えておく
                // ( 2分探索木の性質上, 左の子は存在しない )
            //    minElement->parent->left = minElement->right;
            //    minElement->right->parent = minElement->parent;
            //}

            if( minElement != tree->right )
            {
            	// 右側に要素が, 1つ以上ある時
            	minElement->right = tree->right;
            }

            // 左側の要素の置き換え
            minElement->left = tree->left;
            tree->left->parent = minElement;

            // 親の置き換え
            minElement->parent->left = NULL;
            minElement->parent = tree->parent;

            // 全体の置き換え
            if( tree->key < tree->parent->key )
            {
                // 削除要素自身が左の子の時
                tree->parent->left = minElement;
            }
            else
            {
                // 削除要素自身が右の子の時
                tree->parent->right = minElement;
            }

            delete tree;

        }
        else
        {
            // 削除要素が子を1つ持つ時
            Node *child;

            if( tree->left != NULL )
            {
                // 削除要素の左側に子が存在
                tree->left->parent = tree->parent;
                child = tree->left;
            }
            else
            {
                // 削除要素の右側に子が存在
                tree->right->parent = tree->parent;
                child = tree->right;
            }

            if( tree->key < tree->parent->key )
            {
                // 削除要素自身が左の子の時
                tree->parent->left = child;
            }
            else
            {
                // 削除要素自身が右の子の時
                tree->parent->right = child;
            }

            // 要素を削除する
            delete tree;

        }
    }


    return ret;
}

// ----------▲▲▲▲▲ 2分探索木の操作関数　▲▲▲▲▲----------

// ----------▼▼▼▼▼ 巡回関連の関数　▼▼▼▼▼----------

// 先行順巡回
// 根節点、左部分木、右部分木の順で節点を巡回
void preorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    printf(" %d", Tree->key);
    preorderTreeWalk(Tree->left);
    preorderTreeWalk(Tree->right);

    return;
}

int pre_right = 0;

// 中間順巡回
// 左部分木、根節点、右部分木の順で節点を巡回
void inorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    inorderTreeWalk(Tree->left);
    printf(" %d", Tree->key);
    inorderTreeWalk(Tree->right);

    return;
}

// 後行順巡回
// 左部分木、右部分木、根節点の順で節点を巡回
void postorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    postorderTreeWalk(Tree->left);
    postorderTreeWalk(Tree->right);
    printf(" %d", Tree->key);

    return;
}

// ----------▲▲▲▲▲ 巡回関連の関数　▲▲▲▲▲----------



Measured memory_bytes: 21904