#include <iostream>

using namespace std;

struct node {
    int data;
    node *left;
    node *right;
    node(int dataofNode){
        data=dataofNode;
        left=NULL;
        right=NULL;
    }
};

node* insert(node *&root, int element){
    if(root==NULL){
        root=new node(element);
        root->right=NULL;
        root->left=NULL;

    } else if(root->data>=element){
        root->left=insert(root->left,element);

    } else{
        root->right=insert(root->right, element);
    }
    return root;
}

string find(node *root, int element) {
    if (root == NULL) {
        cout << "tree is empty!";
    }
    else if (root->data == element) {
        cout << "is included";
    }
    else {
        if (root->data < element) {
            if (root->right) {
                 find(root->right, element);
            }
            else {
                cout << "Excluded";
            }
        }
        else {
            if (root->left) {
                 find(root->left, element);
            }
            else {
                cout << "Excluded";
            }
        }
    }
}

void print_Tree(node *root){
    if(root!=NULL){
        print_Tree(root->left);
        cout<<root->data<<" ";
        print_Tree(root->right);
    }
}


void qprint(node *root, int u) {
    if (root == NULL){
        return;
    }

    else {
        qprint(root->right, ++u);
        for (int i = 0; i < u; ++i){
            cout << "  ";
        }
        cout << root->data << endl;
        u--;
        qprint(root->left, ++u);
    }
}
void PrintTree (node *root,int n)
{
    if (root) {
        PrintTree(root->right,n+1);

        for (int i = 0; i < n ; ++i) {
            cout <<"   ";
        }
        cout << root->data << endl;


        PrintTree(root->left,n+1);
    }

}
node* deletetree(node* root,int n)
{
    if (root==NULL) {
        return root;
    }
    else if (root->data> n) {
        root->left = deletetree(root->left, n);
    }
    else if (root->data<n) {
        root->right=deletetree(root->right,n);
    }
    else {
        if(root->left==NULL&&root->right==NULL)
        {
            delete root;
            root=NULL;
        }
        else if (root->left==NULL && root->right!=NULL){
            node* current=root;
            root=root->right;
            delete current;
        }
        else if (root->left!=NULL && root->right==NULL){
            node* current=root;
            root=root->left;
            delete current;
        }
        else {
            node* current=root->right;
            root->data=current->data;
            root->right=deletetree(root->right,current->data);
        }
    }

    return root;
}


int main() {
  /* int array[]={5,4,6,2,5,3,6,7,9,8};
   node *root=NULL;
    for(int i=0; i<10;i++){
       root=insert(root, array[i]);

  }*/
    /*print(root);*/
    /*find(root, 11);*/




    auto *a = new node(5);
    auto *b = new node(4);
    auto *c = new node(6);
    auto *d = new node(2);
    auto *e = new node(5);
    auto *f = new node(3);
    auto *g = new node(6);
    auto *h = new node(7);
    auto *i = new node(9);
    auto *j = new node(8);


    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    d->right = f;
    c->right = g;
    g-> right = h;
    h->right = i;
    i->left = j;
    /*qprint(a,6 );*/
    deletetree(a,7);
    PrintTree(a ,5);
    return 0;
}