#include <iostream>
#include <cstdlib>

using namespace std;

class BinarySearchTree{
    private:
        struct tree_node{
           tree_node* left;
           tree_node* right;
           int data;
           string name;
        };
        tree_node* root;
    public:
        BinarySearchTree(){
           root = NULL;
        }
        bool isEmpty() const { return root==NULL; }
        void print_preorder();
        void preorder(tree_node*);
        void insert(int d, string  n);
        void remove(string  n);
        void find(string  key);
};
void BinarySearchTree::insert(int d, string  n){
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->name = n;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;
    if(isEmpty()) root = t;
    else{//åñëè äåðåâî íå ïóñòîå -> ñîçäàåì ïîääåðåâî
        tree_node* curr;
        curr = root;
        while(curr){
            parent = curr;
            if(t->name > curr->name) curr = curr->right;
            else curr = curr->left;
        }
        if(t->name < parent->name)parent->left = t;
        else parent->right = t;
    }
}
void BinarySearchTree::remove(string  n){
    bool found = false;
    if(isEmpty()){
        cout<<" The telephone book is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL){
         if(curr->name == n){
            found = true;
            break;
         }
         else{
             parent = curr;
             if(n>curr->name) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found){
        cout<<" The contact wasn`t found! "<<endl;
        return;
    }
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL)){
       if(curr->left == NULL && curr->right != NULL){
          if(parent->left == curr){
             parent->left = curr->right;
             delete curr;
          }
          else{
             parent->right = curr->right;
             delete curr;
          }
       }
       else{
          if(parent->left == curr){
             parent->left = curr->left;
             delete curr;
          }
          else{
             parent->right = curr->left;
             delete curr;
          }
       }
     return;
    }
//óçåë áåç äåòåé
   if( curr->left == NULL && curr->right == NULL){
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
        delete curr;
        return;
    }
//óçåë ñ äâóìÿ äåòüìè
    if (curr->left != NULL && curr->right != NULL){
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL)){
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else{
            if((curr->right)->left != NULL){
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL){
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
                curr->name = lcurr->name;
                curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
            }
            else{
               tree_node* tmp;
               tmp = curr->right;
               curr->name = tmp->name;
               curr->data = tmp->data;
               curr->right = tmp->right;
               delete tmp;
           }
        }
         return;
    }
}
void BinarySearchTree::print_preorder(){
    preorder(root);
}

void BinarySearchTree::preorder(tree_node* p){
    if(p != NULL){
        cout<<" "<<p->name<<" : "<<p->data<<endl;
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}
void BinarySearchTree::find(string  key){
    bool found = false;
    if(isEmpty()){
        cout<<" The telephone book is empty "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL){
         if(curr->name == key){
            found = true;
            cout << "Number " << key << " - " << curr->data << endl;
            break;
         }
         else{
             parent = curr;
             if(key>curr->name) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found){
        cout<<" The contact wasn`t found! "<<endl;
        return;
    }
}

int main()
{
    BinarySearchTree b;
    int ch,tmp,n;
    string  n1, n2;
    while(1)
    {
       cout<< endl;
       cout<<" 1. Add a new member "<<endl;
       cout<<" 2. Tree output "<<endl;
       cout<<" 3. Delete member "<<endl;
       cout<<" 4. Search the number "<<endl;
        cout<<" Your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter the name: ";
                    cin>>n1;
                    cout<<" Enter the number: ";
                    cin>>tmp;
                    b.insert(tmp,n1);
                    break;

           case 2 : cout<<endl;
                    cout<<" Tree output: "<<endl;
                    b.print_preorder();
                    break;

           case 3 : cout<<" Enter the member to delete: ";
                    cin>>n2;
                    b.remove(n2);
                    break;
           case 4 : cout<<" Enter the name for searching: ";
                    cin>>n2;
                    b.find(n2);
                    break;
       }
    }
}