#include <stdio.h>
#include <stdlib.h>

struct node
{
    struct node *right, *left, *parent;
    int key;
};

typedef struct node *Node;
#define NIL NULL
Node root;
void insert(int);
void inorder(Node);
void preorder(Node);
Node treeSearch(Node, int);
Node treeMinimum(Node);
Node treeMaximum(Node);
Node treeSuccessor(Node);
void treeDelete(Node);

int main()
{
    int n, i, x;
    char com[20];
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%s", com);
        if (strcmp(com, "find") == 0)
        {
            scanf("%d", &x);
            Node t = treeSearch(root, x);
            if (strcmp(com, "findMin") == 0)
            {
                Node minn = treeMinimum(t);
                printf("%d\n", minn->key);
            }
            else if (strcmp(com, "findMax") == 0)
            {
                Node maxn = treeMaximum(t);
                printf("%d\n", maxn->key);
            }
            else
            {
                if (t != NIL)
                {
                    printf("yes\n");
                }
                else
                {
                    printf("no\n");
                }
            }
        }
        else if (com[0] == 'i')
        {
            scanf("%d", &x);
            insert(x);
        }
        else if (strcmp(com, "print") == 0)
        {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
        else if (strcmp(com, "delete") == 0)
        {
            scanf("%d", &x);
            treeDelete(treeSearch(root, x));
        }
    }
    return 0;
}

void insert(int k)
{
    int H;
    Node y;
    Node x;
    Node z;
    y = NIL;
    x = root;
    z = malloc(sizeof(struct node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    while (x != NIL)
    {
        y = x;
        if (z->key < x->key)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == NIL)
    {
        root = z;
    }
    else
    {
        if (z->key < y->key)
        {
            y->left = z;
        }
        else
        {
            y->right = z;
        }
    }
}

void inorder(Node u)
{
    if (u == NIL)
        return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node u)
{
    if (u == NIL)
        return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

Node treeSearch(Node u, int k)
{
    while (u != NIL && k != u->key)
    {
        if (k < u->key)
        {
            u = u->left;
        }
        else
        {
            u = u->right;
        }
    }
    return u;
}

Node treeMinimum(Node x)
{
    while (x->left != NIL)
    {
        x = x->left;
    }
    return x;
}

Node treeMaximum(Node x)
{
    while (x->right != NIL)
    {
        x = x->right;
    }
    return x;
}

Node treeSuccessor(Node x)
{
    if (x->right != NIL)
    {
        return treeMinimum(x->right);
    }
    Node y = x->parent;
    while (y != NIL && x == y->right)
    {
        x = y;
        y = y->parent;
    }
    return y;
}

void treeDelete(Node z)
{
    Node y;
    Node x;
    if (z->left == NIL || z->right == NIL)
    {
        y = z;
    }
    else
    {
        y = treeSuccessor(z);
    }
    if (y->left != NIL)
    {
        x = y->left;
    }
    else
    {
        x = y->right;
    }
    if (x != NIL)
        x->parent = y->parent;

    if (y->parent == NIL)
    {

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

    if (y != z)
    {

        z->key = y->key;
    }

    free(y);
}


Measured memory_bytes: 20480