#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int code;
    struct node *left, *right;
} Node;

Node * createNode()
{
    Node *new = (Node *) malloc(sizeof(Node));
    printf("Code: ");
    scanf("%d", &new->code);
    new->left = NULL;
    new->right = NULL;

    return new;
}

Node * insNode(Node *root, Node *new)
{
    if (root == NULL) return new;
    else if (new->code < root->code) root->left = insNode(root->left, new);
    else root->right = insNode(root->right, new);
    return root;
}

void prntTree(Node *root)
{
    if (root == NULL) return;
    prntTree(root->left);
    printf("%d ", root->code);
    prntTree(root->right);
}

Node * searchTree(Node *root, int targ)
{
    while (root != NULL){
        if (root->code == targ){
            printf("Product found. Code: %d", root->code);
            return root;
        }
        if (targ < root->code) root = root->left;
        else root = root->right;
    }
    printf("Product not found.");
    return NULL;
}

Node * findClosest(Node *root)
{
    Node *big, *small, *aux;

    aux = root->left;
    while (1){
        if (aux->right == NULL){
            big = aux;
            break;
        }
        aux = aux->right;
    }

    aux = root->right;
    while (1){
        if (aux->left == NULL){
            small = aux;
            break;
        }
        aux = aux->left;
    }

    if (root->code - big->code < small->code - root->code) return big;
    else return small;
}

void delNode(Node *root)
{
    Node *leaf, **nroot;
    int found = 0, target;

    printf("\nNode to be removed: ");
    scanf("%d", &target);
    printf("\n");

    while (root != NULL){
        if (root->code == target){
            nroot = &root;
            found = 1;
            break;
        }
        if (target < root->code) root = root->left;
        else root = root->right;
    }

    if (!found){
    printf("Node not found.");
    return;
    }

    if ((*nroot)->left == NULL && (*nroot)->right == NULL) *nroot = NULL;
    else if ((*nroot)->left != NULL) *nroot = (*nroot)->left;
    else if ((*nroot)->right != NULL) *nroot = (*nroot)->right;
    else {
        leaf = findClosest(*nroot);
        *nroot = leaf;
        leaf = NULL;
        free(leaf);
    }
    if (*nroot == NULL) free(*nroot);
    return;
}

int main()
{
    Node *root = NULL;
    for (int i=0; i<10; i++){
        if (root == NULL) root = insNode(root, createNode());
        else insNode(root, createNode());
    }
    printf("\n");
    prntTree(root);
    printf("\n");
    delNode(root);
    prntTree(root);
    return 0;
}