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

#define A_MAX 500000
#define INVALID -2000000000

typedef struct _tree {
    struct _tree *parent;
    struct _tree *left;
    struct _tree *right;
    int key;
} Tree;

void preorder_debug(Tree *node) 
{
    printf(" %d", node->key);
    if (node->parent!= NULL) {
        printf(" p %d", node->parent->key);
    }
    else {
        printf(" p NULL");
    }
    if (node->left != NULL) {
        printf(" l %d", node->left->key);
    }
    else {
        printf(" l NULL");
    }
    if (node->right != NULL) {
        printf(" r %d", node->right->key);
    }
    else {
        printf(" r NULL");
    }
    printf("\n");


    if (node->left != NULL) {
        preorder_debug(node->left);
    }
    if (node->right != NULL) {
        preorder_debug(node->right);
    }
    
    return;
}


void preorder(Tree *node) 
{
    printf(" %d", node->key);
    if (node->left != NULL) {
        preorder(node->left);
    }
    if (node->right != NULL) {
        preorder(node->right);
    }
    
    return;
}

void inorder(Tree *node) 
{
    if (node->left == NULL) {
        printf(" %d", node->key);
    }
    else {
        inorder(node->left);
        printf(" %d", node->key);
    }
    if (node->right != NULL) {
        inorder(node->right);
    }
    
    return;
}

void postorder(Tree* node) 
{
    if (node->left != NULL) {
        postorder(node->left);
    }

    if (node->right != NULL) {
        postorder(node->right);
    }
    
    printf(" %d", node->key);

    return;
}


Tree* insert(Tree* root, Tree* node) {
    Tree* y = NULL;
    Tree* x = root;
    
//    if (root != NULL) {
//        printf("   root %d\n", root->key);
//    } else {
//        printf("   root NULL\n");
//    }
    
    while (x != NULL) {
        y = x;
        if (node->key < x->key) {
            x = x->left;
        }
        else {
            x = x->right;
        }
    }
    node->parent = y;
    if (y == NULL) {
        root = node;
    }
    else if (node->key < y->key) {
        y->left = node;
    }
    else {
        y->right = node;
    }
    
    /*
    if (y != NULL) {
        printf("   p %d\n", y->key);
    }
    else {
        printf("   p NULL\n");
    }
    if (root != NULL) {
        printf("   return root %d\n", root->key);
    } else {
        printf("   return root NULL\n");
    }
    */
    
    return root;
}

Tree* find(Tree* root, int key) {
    Tree* node = root;
    while (node != NULL) {
        if (node->key == key) break;
        else if (node->key > key) {
            node = node->left;
        } else {
            node = node->right;
        }
    }
    return node;
}

Tree* get_minimum(Tree* node) {
    Tree* min = node;
    while (min->left != NULL) {
        min = min->left;
    }
    return min;
}

Tree* get_next(Tree* node) {
    Tree* next;
    if (node->right != NULL) {
        next = get_minimum(node->right);
        /*
        if (next != NULL) {
            printf("get_min : %d\n", next->key);
        }
        else {
            printf("get_min : NULL\n");
        }
        */
    }
    else  {
        next = node;
        while (next != NULL) {
            if (next->parent->left == next) {
                next = next->parent;
                break;
            }
            next = next->parent;
        }
        /*
        if (next != NULL) {
            printf("next parent : %d\n", next->key);
        }
        else {
            printf("next parent : NULL\n");
        }
        */
    }

    return next;
}

Tree* delete_node(Tree* root, Tree* node) {
    Tree *x, *y;
    if (node->left == NULL || node->right == NULL) {
        y = node;
    }
    else {
        y = get_next(node);
    }

    if (y->left != NULL) {
        x = y->left;
    } 
    else {
        x = y->right;
    }

    if (x != NULL) {
        x->parent = y->parent;
    }

    if (y->parent == NULL) {
        root = x;
    }
    else if (y == y->parent->left) {
        y->parent->left = x;
    }
    else {
        y->parent->right = x;
    }
    
    if (y != node) {
        node->key = y->key;
    }

    delete y;

    return root;
}


int main() {
    int m;
    int key;
    char order[10];
    Tree* root = NULL;

    cin >> m;


    for (int i = 0; i < m; i++) {
//        printf("i %d\n", i);
        scanf("%s", order);
        if (strcmp(order, "insert") == 0) {
            Tree* node = new Tree;
            cin >> key;
            node->parent = NULL;
            node->left = NULL;
            node->right = NULL;
            node->key = key;
            root = insert(root, node);
//            printf("insert %d\n", key);
//            preorder_debug(root);
//            cout << endl;
        }
        else if (strcmp(order, "find") == 0) {
            cin >> key;
            if (find(root, key) != NULL) {
                cout << "yes" << endl;
            }
            else {
                cout << "no" << endl;
            }
        }
        else if (strcmp(order, "delete") == 0) {
            cin >> key;
            Tree* node = find(root, key);
//            printf("delete %d\n", key);
//            preorder_debug(root);
            root = delete_node(root, node);
//            printf("-------\n");
//            preorder_debug(root);
//            cout << endl;
        }
        else if (strcmp(order, "print") == 0) {
//            printf("#print\n");
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 21952