#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>

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

void binarySearchTreeInsert(Node** rootAddr, int val);

Node* binarySearchTreeSearch(Node* root, int val, int mode);
Node* binarySearchTreeSearchRecursively(Node* root, int val);
Node* binarySearchTreeSearchLoop(Node* root, int val);

void binarySearchTreeDelete(Node** rootAddr, int val);

Node* nextNodeInInOrder(Node* node);
Node* getMinimumNode(Node* node);
void treeWalk(int** arrAddr, Node* root, int mode);
void freeBinarySearchTree(Node* root);

void print(Node* root, int size, int* in, int* pre);

int main(int argc, char** argv) {
    int len, *in, *pre, nrOfNodes;
    std::string cmd;
    Node* root;

    nrOfNodes = 0;
    root = nullptr;

    scanf("%d", &len);
    for (int i = 0; i < len; i++) {
        std::cin >> cmd;
        if (cmd == "insert") {
            nrOfNodes++;
            int val;
            scanf("%d", &val);
            binarySearchTreeInsert(&root, val);
        } else if (cmd == "print") {
            print(root, nrOfNodes, in, pre);
        } else if (cmd == "find") {
            int val;
            scanf("%d", &val);
            printf("%s\n", binarySearchTreeSearch(root, val, 1) != nullptr ? "yes" : "no");
        } else if (cmd == "delete") {
            nrOfNodes--;
            int val;
            scanf("%d", &val);
            binarySearchTreeDelete(&root, val);
        }
    }

    freeBinarySearchTree(root);
    return 0;
}

void print(Node* root, int size, int* in, int* pre) {
    int *inPtr, *prePtr;

    in = (int *) calloc(sizeof(int), size + 1);
    inPtr = in;
    pre = (int *) calloc(sizeof(int), size + 1);
    prePtr = pre;

    treeWalk(&inPtr, root, 1);
    treeWalk(&prePtr, root, 0);

    for (int i = 0; i < size; i++) {
        printf(" %d", *(in + i));
    }
    printf("\n");

    for (int i = 0; i < size; i++) {
        printf(" %d", *(pre + i));
    }
    printf("\n");

    free(in);
    free(pre);
}

/* unbalanced tree */
void binarySearchTreeInsert(Node** rootAddr, int val) {
    Node *newNode, *parent;
    
    newNode = (Node *) calloc(sizeof(Node), 1);
    newNode->parent = newNode->left = newNode->right = nullptr;
    newNode->key = val;

    parent = *rootAddr;

    while (true) {
        if (parent != nullptr) {
            if (parent->key > val) {
                if (parent->left != nullptr) {
                    parent = parent->left;
                } else {
                    break;
                }
            } else {
                if (parent->right != nullptr) {
                    parent = parent->right;
                } else {
                    break;
                }
            }
        } else {
            break;
        }
    }

    newNode->parent = parent;
    if (parent != nullptr) {
        if (parent->key > val) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }
    } else {
        *rootAddr = newNode;
    }
}

Node* binarySearchTreeSearch(Node* root, int val, int mode) {
    if (mode == 0) {
        // recursion
        return binarySearchTreeSearchRecursively(root, val);
    } else if (mode == 1) {
        // loop
        return binarySearchTreeSearchLoop(root, val);
    } else {
        return nullptr;
    }
}

Node* binarySearchTreeSearchRecursively(Node* root, int val) {
    if (root == nullptr) {
        return nullptr;
    }

    if (root->key == val) {
        return root;
    } else if (root->key > val) {
        return binarySearchTreeSearchRecursively(root->left, val);
    } else {
        return binarySearchTreeSearchRecursively(root->right, val);
    }
}

Node* binarySearchTreeSearchLoop(Node* root, int val) {
    while (root != nullptr) {
        if (root->key == val) {
            return root;
        } else if (root->key > val) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return nullptr;
}

void binarySearchTreeDelete(Node** rootAddr, int val) {
    Node* foundNode; // node with the value to be deleted
    Node* deletedNode; // node to be deleted
    Node* childOfDeletedNode;

    foundNode = binarySearchTreeSearchLoop(*rootAddr, val);

    if (foundNode != nullptr) {
        if (foundNode->left == nullptr || foundNode->right == nullptr) {
            deletedNode = foundNode;
        } else {
            deletedNode = nextNodeInInOrder(foundNode);
        }

        if (deletedNode->left != nullptr) {
            childOfDeletedNode = deletedNode->left;
        } else {
            childOfDeletedNode = deletedNode->right;
        }

        if (childOfDeletedNode != nullptr) {
            childOfDeletedNode->parent = deletedNode->parent;
        }

        if (deletedNode->parent == nullptr) {
            *rootAddr = childOfDeletedNode;
        } else if (deletedNode->parent->left == deletedNode) {
            deletedNode->parent->left = childOfDeletedNode;
        } else {
            deletedNode->parent->right = childOfDeletedNode;
        }

        if (deletedNode != foundNode) {
            foundNode->key = deletedNode->key;
        }

        free(deletedNode);
        deletedNode = nullptr;
    } else {
        printf("%d is not in the tree!\n", val);
        return;
    }
}

/* mode: 0 - preorder; 1 - inorder; 2 - postorder */
void treeWalk(int** arrAddr, Node* root, int mode) {
    if (root == nullptr) {
        return;
    }

    if (mode == 0) {
        // preorder
        *(*arrAddr)++ = root->key;
    }

    treeWalk(arrAddr, root->left, mode);

    if (mode == 1) {
        // inorder
        *(*arrAddr)++ = root->key;
    }

    treeWalk(arrAddr, root->right, mode);

    if (mode == 2) {
        // postorder
        *(*arrAddr)++ = root->key;
    }
}

void freeBinarySearchTree(Node* root) {
    if (root == nullptr) {
        return;
    }

    freeBinarySearchTree(root->left);
    freeBinarySearchTree(root->right);

    free(root);
    root = nullptr;
}

Node* nextNodeInInOrder(Node* node) {
    if (node->right != nullptr) {
        return getMinimumNode(node->right);
    } else {
        Node* parentNode = node->parent;
        while (parentNode != nullptr && parentNode->right == node) {
            node = parentNode;
            parentNode = parentNode->parent;
        }

        return parentNode;
    }
}

Node* getMinimumNode(Node* node) {
    while (node->left != nullptr) {
        node = node->left;
    }

    return node;
}



Measured memory_bytes: 24812