#include <stdio.h>
#define MAX 500001
int N;
char inst[7];


class Node {
public:
    Node();
    int key;
    int val;
    Node* left;
    Node* right;
    Node* parent;
};

Node::Node()
{
    left = NULL;
    right = NULL;
    parent = NULL;
}

class BST {
public:
    BST();
    Node* tree[MAX];
    Node* root;
    int size;
    void insertKey(int key);
    Node* findKey(int key);
    void deleteKey(int key);
    void printInOrder(Node* node);
    void printPreOrder(Node* node);
    Node* getMin(Node* node);
    Node* getMax(Node* node);
    Node* getSuccessor(Node* node);
    void doTransplant(Node* old_node, Node* new_node);
    
};

BST::BST()
{
    size = 0;
    root = NULL;
}

void BST::insertKey(int key)
{
    Node* node = new Node;
    node->key = key;
    node->val = key;
    
    Node* parent_node = NULL;
    Node* compared_node = root;
    while (compared_node != NULL) {
        parent_node = compared_node;
        if (node->key < compared_node->key) {
            compared_node = compared_node->left;
        } else {
            compared_node = compared_node->right;
        }
    }
    node->parent = parent_node;
    if (parent_node == NULL) {
        root = node;
    } else if (node->key < parent_node->key) {
        parent_node->left = node;
    } else {
        parent_node->right = node;
    }
}

Node* BST::findKey(int key)
{
    Node* inspected_node = root;
    while (inspected_node != NULL) {
        if (key < inspected_node->key) {
            inspected_node = inspected_node->left;
        } else if (key > inspected_node->key) {
            inspected_node = inspected_node->right;
        } else {
            break;
        }
    }
    return inspected_node;
}

void BST::printInOrder(Node* node)
{
    if (node != NULL) {
        printInOrder(node->left);
        printf(" %d", node->key);
        printInOrder(node->right);
    }
}

void BST::printPreOrder(Node* node)
{
    if (node != NULL) {
        printf(" %d", node->key);
        printPreOrder(node->left);
        printPreOrder(node->right);
    }
}

Node* BST::getMin(Node* node)
{
    Node* min_node = node;
    while(min_node->left != NULL)
        min_node = min_node->left;
    return min_node;
}

Node* BST::getMax(Node* node)
{
    Node* max_node = node;
    while (max_node->right != NULL)
        max_node = max_node->right;
    return max_node;
}

Node* BST::getSuccessor(Node* node)
{
    Node* successor = NULL;
    if (node->right != NULL) {
        successor = getMin(node->right);
    } else {
        Node* parent_node = node->parent;
        while (parent_node != NULL && node == parent_node->right) {
            node = parent_node;
            parent_node = node->parent;
        }
        successor = parent_node;
    }
    return successor;
}

void BST::doTransplant(Node* old_node, Node* new_node)
{
    if (old_node->parent == NULL) {
        root = new_node;
    } else if (old_node == old_node->parent->left) {
        old_node->parent->left = new_node;
    } else {
        old_node->parent->right = new_node;
    }
    if (new_node != NULL)
        new_node->parent = old_node->parent;
}

void BST::deleteKey(int key)
{
    Node* to_be_deleted = findKey(key);
    if (to_be_deleted) {
        if (to_be_deleted->left == NULL) {
            doTransplant(to_be_deleted, to_be_deleted->right);
        } else if (to_be_deleted->right == NULL) {
            doTransplant(to_be_deleted, to_be_deleted->left);
        } else {
            Node* replace = getMin(to_be_deleted->right);
            if (replace->parent != to_be_deleted) {
                doTransplant(replace, replace->right);
                replace->right = to_be_deleted->right;
                replace->right->parent = replace;
            }
            doTransplant(to_be_deleted, replace);
            replace->left = to_be_deleted->left;
            replace->left->parent = replace;
        }
    }
}

int main(void)
{
    //freopen("in.txt", "r", stdin);
    BST bst;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%s", inst);
        int k;
        if (inst[0] == 'i') {
            scanf("%d", &k);
            bst.insertKey(k);
        } else if (inst[0] == 'f') {
            scanf("%d", &k);
            Node* founded = bst.findKey(k);
            if (founded) {
                printf("yes\n");
            } else {
                printf("no\n");
            }
        } else if (inst[0] == 'd') {
            scanf("%d", &k);
            bst.deleteKey(k);
        } else {
            bst.printInOrder(bst.root);
            printf("\n");
            bst.printPreOrder(bst.root);
            printf("\n");
        }
    }
    return 0;
}

Measured memory_bytes: 21472