#include <bits/stdc++.h>
using namespace std;

class BinarySearchTree {
private:
        struct Node {
                int key;
                Node *parent, *left, *right;
                Node () : parent(nullptr), left(nullptr), right(nullptr) {}
                Node (int key) : key(key), parent(nullptr), left(nullptr), right(nullptr) {}
        };
public:
        BinarySearchTree () : root(nullptr) {}

        void insert(int k)
        {
                Node *data;
                Node **pos = find(k, &root);
                if ( *pos == nullptr ) {
                        data = new Node(k);
                        *pos = data;
                        data->parent = *pos;
                }
        }

        void remove(int k)
        {
                Node **pos = find(k, &root);
                Node **delnode, *tmp;

                if ( *pos == nullptr ) return;
                if ( (*pos)->left == nullptr || (*pos)->right == nullptr ) delnode = pos;
                else delnode = getSuccessor(pos);

                (*pos)->key = (*delnode)->key;

                tmp = *delnode;
                *delnode = nullptr;
                if ( tmp->left != nullptr ) *delnode = tmp->left;
                if ( tmp->right != nullptr ) *delnode = tmp->right;
                delete(tmp);
        }

        bool find(int k) { return ( *find(k, &root) != nullptr ); }
        void preorder() { preorder(root); }
        void inorder() { inorder(root); }
private:
        Node *root;

        Node** getSuccessor(Node **node)
        {
                if ( (*node)->right != nullptr ) return ( getMinimum(&((*node)->right)) );

                Node *x = *node, *y = x->parent;
                while ( y != nullptr && y->right == x ) {
                        x = y;
                        y = x->parent;
                }
                return &(x->parent);
        }

        Node** getMinimum(Node **node)
        {
                if ( (*node)->left == nullptr ) return ( node );
                return ( getMinimum(&((*node)->left)) );
        }

        Node** find(int k, Node **node)
        {
                if ( *node == nullptr || (*node)->key == k ) return ( node );
                if ( k < (*node)->key ) return ( find(k, &((*node)->left)) );
                else return ( find(k, &((*node)->right)) );
        }

        void preorder(Node *node)
        {
                if ( node == nullptr ) return;
                cout << " " << node->key;
                preorder(node->left);
                preorder(node->right);
        }

        void inorder(Node *node)
        {
                if ( node == nullptr ) return;
                inorder(node->left);
                cout << " " << node->key;
                inorder(node->right);
        }
};


int main()
{
        int n;
        BinarySearchTree tree;

        cin >> n;
        for ( int i = 0; i < n; i++ ) {
                string S;
                int k;
                cin >> S;
                if ( S == "insert" ) {
                        cin >> k;
                        tree.insert(k);
                } else if ( S == "print" ) {
                        tree.inorder(); cout << endl;
                        tree.preorder(); cout << endl;
                } else if ( S == "find" ) {
                        cin >> k;
                        if ( tree.find(k) ) cout << "yes" << endl;
                        else cout << "no" << endl;
                } else if ( S == "delete" ) {
                        cin >> k;
                        tree.remove(k);
                }
        }

        return ( 0 );
}



Measured memory_bytes: 21808