// Refernce : Eternally Confuzzled Website


#include <bits/stdc++.h>
#define NUMBER_OF_NODES 100000
#define LL long long
#define height(p) ((p) == NULL ? -1 : (p)->balance)
#define jsw_max(a,b) ((a) > (b) ? (a) : (b))
using namespace std;



struct AVL_node
{
    LL data;
    LL balance;
    struct AVL_node *link[2];
};



LL height1(struct AVL_node * root)
{
   if(root==NULL) return 0;
   else
     return 1+max(height1(root->link[0]),height1(root->link[1]));
}


struct AVL_tree
{
    struct AVL_node *root;
};

int jsw_find(struct AVL_tree *tree, LL item)
{
    struct AVL_node *it = tree->root;

    while (it != NULL)
    {
        if (it->data == item)
        {
            return 1;
        }
        else
        {
            int dir = it->data < item;

            it = it->link[dir];
        }
    }

    return 0;
}


struct AVL_node *make_node(LL data)
{
    //cout<<" I reached here 3a"<<endl;
    struct AVL_node *rn = (struct AVL_node *) malloc(sizeof *rn);
    // cout<<" I reached here 4"<<endl;
    if (rn != NULL)
    {
        rn->data = data;
        rn->link[0] = rn->link[1] = NULL;
    }

    return rn;
}

struct AVL_node *jsw_single(struct AVL_node *root, LL dir)
{
    struct AVL_node *save = root->link[!dir];

    root->link[!dir] = save->link[dir];
    save->link[dir] = root;

    return save;
}

struct AVL_node *jsw_double(struct AVL_node *root, LL dir)
{
    struct AVL_node *save = root->link[!dir]->link[dir];

    root->link[!dir]->link[dir] = save->link[!dir];
    save->link[!dir] = root->link[!dir];
    root->link[!dir] = save;

    save = root->link[!dir];
    root->link[!dir] = save->link[dir];
    save->link[dir] = root;

    return save;
}

void jsw_adjust_balance(struct AVL_node *root, LL dir, LL bal)
{
    struct AVL_node *n = root->link[dir];
    struct AVL_node *nn = n->link[!dir];

    if (nn->balance == 0)
    {
        root->balance = n->balance = 0;
    }
    else if (nn->balance == bal)
    {
        root->balance = -bal;
        n->balance = 0;
    }
    else /* nn->balance == -bal */
    {
        root->balance = 0;
        n->balance = bal;
    }

    nn->balance = 0;
}

struct AVL_node *AVL_node_insert_balance(struct AVL_node *root, LL dir)
{
    struct AVL_node *n = root->link[dir];
    LL bal = dir == 0 ? -1 : +1;

    if (n->balance == bal)
    {
        root->balance = n->balance = 0;
        root = jsw_single(root, !dir);
    }
    else /* n->balance == -bal */
    {
        jsw_adjust_balance(root, dir, bal);
        root = jsw_double(root, !dir);
    }

    return root;
}

//struct AVL_node *AVL_node_insert_r(struct AVL_node *root, LL item, LL *done) {
//
//    cout<<" I reached here 2"<<endl;
//    if (root == NULL) {
//        root = make_node(item);
//        cout<<" I reached here 3"<<endl;
//    } else {
//         cout<<" I reached here 2a"<<endl;
//
//                 int dir = ((root->data) < item);
//
//       //  cout<<" (root->data) :"<<(root->data)<<" data : "<<data<<endl;
//
//          cout<<" I reached here 2Aaa"<<endl;
//        root->link[dir] = AVL_node_insert_r(root->link[dir], item, done);
//        cout<<" I reached here 2b"<<endl;
//
//        if (!*done) {
//            /* Update balance factors */
//            root->balance += dir == 0 ? -1 : +1;
//
//            /* Rebalance as necessary and terminate */
//            if (root->balance == 0) {
//                *done = 1;
//            } else if (abs(root->balance) > 1) {
//                cout<<" I reached here 2c"<<endl;
//                root = AVL_node_insert_balance(root, dir);
//                *done = 1;
//                cout<<" I reached here 2d"<<endl;
//            }
//        }
//    }
//
//    return root;
//}
struct AVL_node *AVL_node_insert_r(struct AVL_node *root, LL item, LL *done)
{
    if (root == NULL)
    {
        root = make_node(item);
    }
    else
    {
        // cout<<" (root->data)"<< (root->data)<< " item "<<item<<endl;
        int dir = (root->data) < item;
        int lh, rh, max;

        root->link[dir] = AVL_node_insert_r(root->link[dir], item, done);

        if (!*done)
        {
            /* Rebalance if necessary */
            lh = height(root->link[dir]);
            rh = height(root->link[!dir]);

            if (lh - rh >= 2)
            {
                struct AVL_node *a = root->link[dir]->link[dir];
                struct AVL_node *b = root->link[dir]->link[!dir];

                if (height(a) >= height(b))
                {
                    root = jsw_single(root, !dir);
                }
                else
                {
                    root = jsw_double(root, !dir);
                }

                *done = 1;
            }

            /* Update balance factors */
            lh = height(root->link[dir]);
            rh = height(root->link[!dir]);
            max = jsw_max(lh, rh);

            root->balance = max + 1;
        }
    }

    return root;
}

LL AVL_node_insert(struct AVL_tree *tree, LL item)
{
    LL done = 0;
    //cout<<" I reached here 1";

    tree->root = AVL_node_insert_r(tree->root, item, &done);

    return 1;
}

////////////////////////////DELETION/////////////////////////////////

struct AVL_node *AVL_node_remove_balance(struct AVL_node *root, LL dir, LL *done)
{
    struct AVL_node *n = root->link[!dir];
    LL bal = dir == 0 ? -1 : +1;

    if (n->balance == -bal)
    {
        root->balance = n->balance = 0;
        root = jsw_single(root, dir);
    }
    else if (n->balance == bal)
    {
        jsw_adjust_balance(root, !dir, -bal);
        root = jsw_double(root, dir);
    }
    else /* n->balance == 0 */
    {
        root->balance = -bal;
        n->balance = bal;
        root = jsw_single(root, dir);
        *done = 1;
    }

    return root;
}

struct AVL_node *AVL_node_remove_r(struct AVL_node *root, LL data, LL *done)
{
    if (root != NULL)
    {
        LL dir;

        /* Remove node */
        if (root->data == data)
        {
            /* Unlink and fix parent */
            if (root->link[0] == NULL || root->link[1] == NULL)
            {
                struct AVL_node *save;

                dir = root->link[0] == NULL;
                save = root->link[dir];
                free(root);

                return save;
            }
            else
            {
                /* Find inorder predecessor */
                struct AVL_node *heir = root->link[0];

                while (heir->link[1] != NULL)
                {
                    heir = heir->link[1];
                }

                /* Copy and set new search data */
                root->data = heir->data;
                data = heir->data;
            }
        }

        dir = root->data < data;
        root->link[dir] = AVL_node_remove_r(root->link[dir], data, done);

        if (!*done)
        {
            /* Update balance factors */
            root->balance += dir != 0 ? -1 : +1;

            /* Terminate or rebalance as necessary */
            if (abs(root->balance) == 1)
            {
                *done = 1;
            }
            else if (abs(root->balance) > 1)
            {
                root = AVL_node_remove_balance(root, dir, done);
            }
        }
    }

    return root;
}

LL AVL_node_remove(struct AVL_tree *tree, LL data)
{
    LL done = 0;

    tree->root = AVL_node_remove_r(tree->root, data, &done);

    return 1;
}


/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct AVL_node* node)
{
     if (node == NULL)
          return;


     /* then recur on left sutree */
     printPreorder(node->link[0]);
       /* first print data of node */
     printf("%d ", node->data);

     /* now recur on right subtree */
     printPreorder(node->link[1]);
}
int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt","w",stdout);
    struct AVL_tree r1;
    r1.root = NULL;
    LL i, choice, value;

    cin>>choice>>value;
    while(1)
    {

        if (choice == 1)
        {
            LL i = AVL_node_insert(&r1, value);
            if (i != 1) cout << " Couldn't insert the node" << value << endl;
            else cout << " Node inserted -> " << value << endl;
        }
        if (choice == 0)
        {
            LL i = jsw_find(&r1, value);
            if (i != 1) cout << value <<" Not Found " << endl;
            else cout << " Node exists -> " << value << endl;

        }
        if (choice == 2)
        {
            LL j = jsw_find(&r1, value);
            if (j != 1) cout << "Not Found --> " << value << endl;
            else
            {
                LL i = AVL_node_remove(&r1, value);
                if (i != 1) cout << " Couldn't delete the node" << value << endl;
                else cout << " Node deleted -> " << value << endl;
            }
        }
        cin>>choice>>value;
        if(choice == -1) break;
    }
     cout<<" Node --> "<<(*(r1.root)).data;
    cout<<" height --> "<<height1(&(*(r1.root)));
    cout<<" Preorder traversal :"<<endl;
    printPreorder(&(*(r1.root)));

    return 0;
}