#include <iostream>

using namespace std;
class Bi_node
{
    private:
    int val;
    Bi_node* left;
    Bi_node* right;
    public:
    Bi_node(int value = 1){
        val = value;
        left = NULL;
        right = NULL;
    }
    ~Bi_node(){

    }

    Bi_node& add(int a){
        Bi_node* current = this;
        Bi_node* current1 = current;
        Bi_node* x = new Bi_node(a);
        while (current){
            if (current->val == a){
                cout<<"Already suschestvuet"<<endl;
                return *this;
            }
            current1 = current;
            if (x->val < current1->val){
                current = current-> left;
            }
            else {
                current=current-> right;
            }
        }
        if (x->val < current1->val){
            current1->left = x;
        }
        else{
            current1->right = x;
        }
        return *this;
    }
    int search(int a){
        Bi_node* current = this;
        Bi_node* current1 = current;
        while (current){
            current1 = current;
            if (current1->val==a){
                cout<<1;
                return 1;
            }
            if (a < current1->val){

                current = current-> left;
            }
            else {

                current=current-> right;
            }
        }
        if (current1->val==a){
                cout << 1;
                return 1;
            }
        else{
            cout << 0;
            return 0;
        }
    }
    Bi_node* search_for_del(int a){
        Bi_node* current = this;
        Bi_node* current1 = current;
        while (current){
            current1 = current;
            if (current1->val==a){
                return current1;
            }
            if (a < current1->val){
                current = current-> left;
            }
            else {

                current=current-> right;
            }
        }
        if (current1->val==a){
                return current1;
            }
        else {
            return NULL;
        }
    }
    Bi_node* min(){
        Bi_node* current = this;
        Bi_node* current1 = current;
        while(current->left){
            current1 = current;
            current = current->left;
        }
        return current1;
    }
    Bi_node* max(){
        Bi_node* current = this;
        Bi_node* current1 = current;
        while(current->right){
            current1 = current;
            current = current->right;
        }
        return current1;
    }
    Bi_node* search_for_del1(int a){
        Bi_node* current = this;
        Bi_node* current1 = NULL;
        while (current){
            current1=current;
            if (current->val == a){
                return current1;
            }
            if (a < current->val){
                if (current->left->val == a){
                    return current1;
                }
                current = current-> left;
            }
            else {
                if (current->right->val == a){
                    return current1;
                }
                current=current-> right;
            }
        }

    }

    Bi_node& del(int a){
        Bi_node* el = search_for_del(a);
        if (el == NULL){
            cout<<"No element"<<endl;
        }
        if (el->left==NULL && el->right==NULL){
            Bi_node* prev_el = search_for_del1(a);
            if (prev_el->val > a){
                delete prev_el->left;
                prev_el->left = NULL;
                return *this;
            }
            if (prev_el->val < a){
                delete prev_el->right;
                prev_el->right = NULL;
                return *this;
            }
        }
        if (el->left==NULL && el->right!=NULL){
            Bi_node* mini = el->right->min();
            int b = mini -> val;
            if (mini->left!=NULL){
                b = mini->left->val;
            }
            el->val = b;
            if (mini->left == NULL){
                el->right = mini->right;
                delete mini;
            }
            else{
                delete mini->left;
                mini->left = NULL;
            }
            return *this;
        }
        if (el->left!=NULL && el->right==NULL){
            Bi_node* maxi = el->left->max();
            int c = maxi -> val;
            if (maxi->right!=NULL){
            c = maxi ->right-> val;
            }
            el->val = c;
            if (maxi->right == NULL){
                el->left = maxi->left;
                delete maxi;
            }
            else{
                delete maxi->right;
                maxi->right = NULL;
            }
            return *this;
        }
        else {
            Bi_node* maxi = el->left->max();
            Bi_node* mini = el->right->min();
            int b = mini -> val;
            int c = maxi -> val;
            if (maxi->right!=NULL){
                c = maxi ->right-> val;
            }
            if (mini->left!=NULL){
                b = mini->left->val;
            }
            if ((c - a) < (a - b)){
                el->val = c;
                if (maxi->right == NULL){
                    el->left = maxi->left;
                    delete maxi;
                }
                else{
                    delete maxi->right;
                    maxi->right = NULL;
                }
            }
            else{
                el->val = b;
                if (mini->left == NULL){
                    el->right = mini->right;
                    delete mini;
                }
                else{
                    delete mini->left;
                    mini->left = NULL;
                }
            }
            return *this;
        }
    return *this;
    }
    void print(){
        if (left == NULL){
            if (right == NULL){
                cout<<this->val<<" ";
                return;
            }
            cout<<this->val<<" ";
            right->print();
            return;
        }
        left->print();
        if (right == NULL){
            if (left == NULL){
                cout<<this->val<<" ";
                return;
            }
            cout<<this->val<<" ";
            return;
        }
        cout<<this->val<<" ";
        right->print();
    }
    void del_all(){
        if (left){
            left->del_all();
            delete left;
        }
        if (right){
        right->del_all();
        delete right;
        }
    }
};
class Bi_tree
{
  private:
    Bi_node* root;
  public:
    Bi_tree(int a = 20){
      root = new Bi_node(a);
    }
    ~Bi_tree(){
      root->del_all();
    }
    Bi_tree& add1(int a){
      root->add(a);
      return *this;
    }
    int search1(int a){
      int b = root->search(a);
      return b;
    }
    Bi_tree& del1(int a){
      root->del(a);
      return *this;
    }
    void print_tree(){
      root->print();
    }
};
int main()
{
    Bi_node root = Bi_node(15);
    root.add(5);
    root.add(8);
    root.add(10);
    root.add(11);
    root.add(9);
    root.add(4);
    root.add(3);
    root.add(1);
    root.add(2);
    root.add(6);
    root.add(14);
    root.print();
    cout<<endl;
    root.del(4);
    root.del(10);
    root.del(8);
    root.print();
    cout<<endl;
    root.add(17);
    root.add(25);
    root.add(21);
    root.print();
    cout<<endl;
    root.del_all();
    return 0;
}