#include <iostream>
#include <stdlib.h>


typedef struct node {
    int value;
    node* right;
    node* left;
} node;
void cleartree(node* root);
void print_tree(node* rootr);
node* add_node(node* rootr, int value);
node* getmin(node* root);
node* getmax(node* root);
node* deletenode(node* root, int value);


int main()
{
    node* rootr = NULL;

    rootr = add_node(rootr, 45);
    rootr = add_node(rootr, 51);
    rootr = add_node(rootr, 35);
    rootr = add_node(rootr, 23);
    rootr = add_node(rootr, 65);
    rootr = add_node(rootr, 105);
    rootr = add_node(rootr, 57);
    rootr = add_node(rootr, 34);
    rootr = add_node(rootr, 65);
    rootr = add_node(rootr, 45);
    deletenode(rootr, 23);
    print_tree(rootr);
    return 0;
}

node* add_node(node* rootr, int value) {
    node* new_node = (node*)malloc(sizeof(node));
    new_node->value = value;
    new_node->left = NULL;
    new_node->right = NULL;
    if (rootr == NULL) {
        return new_node;
    }
    node* curr = rootr;
    while (curr) {
        if (curr->value == value) {
            free(new_node);
            return rootr;
        }
        if (curr->value < value) {
            if (curr->right != NULL) {
                curr = curr->right;
                continue;
            }
            else {
                curr->right = new_node;
                return rootr;
            }
        }
        if (curr->value > value) {
            if (curr->left != NULL) {
                curr = curr->left;
                continue;
            }
            else {
                curr->left = new_node;
                return rootr;
            }
        }
    }
    return rootr;
}

node* deletenode(node* root, int value) {
    if (!root) {
        return NULL;
    }
    if (root->value > value) {
        root->left = deletenode(root->left, value);
    }
    if (root->value < value) {
        root->right = deletenode(root->right, value);
    }
    if (root->value == value) {
        if (!root->left && !root->right) {
            free(root);
            return NULL;
        }
        node* temp = NULL;
        if (root->left && !root->right) {
            temp = root->left;
            free(root);
            return temp;
        }
        if (!root->left && root->right) {
            temp = root->right;
            free(root);
            return temp;
        }
        if (root->left && root->right) {
            int maxleft = getmax(root->left)->value;
            int minright = getmin(root->right)->value;
            if (root->value - maxleft < minright - root->value) {
                deletenode(root, maxleft);
                root->value = maxleft;
            }
            else {
                deletenode(root, minright);
                root->value = minright;
            }
        }


    }
    return root;
}

void print_tree(node* rootr) {
    if (rootr->left) {
        print_tree(rootr->left);
    }
    printf("%4d", rootr->value);

    if (rootr->right) {
        print_tree(rootr->right);
    }
    return;
}

void cleartree(node* root) {
    if (root) {
        if (root->left) {
            cleartree(root->left);
        }
        if (root->right) {
            cleartree(root->right);
        }
        free(root);
    }
}





node* getmin(node* root) {
    node* temp = root;
    while (temp->left) {
        temp = temp->left;
    }
    return temp;
}
node* getmax(node* root) {
    node* temp = root;
    while (temp->right) {
        temp = temp->right;
    }
    return temp;
}