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


struct node
{
    int value;
    struct node* left;
    struct node* right;
};


struct node* createNode(int value){
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct node* insert(int x , struct node* root){
    if(root==NULL){
        return createNode(x);
    }

    if(x < root->value){
        root->left =  insert(x , root->left);
    }else{
        root->right = insert(x , root->right);
    }

    return root;
}

struct node* findMin(struct node* root){
    if(root == NULL){
        return NULL;
    }

    if(root->left == NULL){
        return root;
    }else{
        return findMin(root->left);
    }

}

struct node* delete(int x , struct node* root){
    if(root==NULL){
        return NULL;
    }
    
    if(x < root->value){
        root->left = delete(x , root->left);
    }else if(x > root->value){
        root->right = delete(x , root->right);
    }else{

        if(root->right && root->left){
            struct node* tmp = findMin(root->right);
            root->value = tmp->value;
            root->right = delete(tmp->value , root->right);
        }else{
            struct node* tmp = root;
            if(root->left == NULL){
                root = root->right;
            }else if(root->right == NULL){
                root = root->left;
            }

            free(tmp);
        }

    }
    return root;
}

void inorder(struct node* root){
    if(root==NULL){
        return;
    }

    inorder(root->left);
    printf("%d" , root->value);
    inorder(root->right);
}

void preorder(struct node* root){
    if(root==NULL){
        return;
    }

    printf("%d" , root->value);
    preorder(root->left);
    preorder(root->right);
}

void postorder(struct node* root){
    if(root==NULL){
        return;
    }

    postorder(root->left);
    postorder(root->right);
    printf("%d" , root->value);
}

int main(){
    struct node* root = NULL;

    printf("🔹 Inserting nodes: 5, 2, 8, 1, 3, 7, 9\n");
    int values[] = {5, 2, 8, 1, 3, 7, 9};
    for (int i = 0; i < 7; i++)
        root = insert(values[i], root);

    printf("\nInorder traversal: ");
    inorder(root);

    printf("\nPreorder traversal: ");
    preorder(root);

    printf("\nPostorder traversal: ");
    postorder(root);

    printf("\n\n🔹 Deleting 8 (node with two children)\n");
    root = delete(8, root);

    printf("Inorder after delete(8): ");
    inorder(root);
    printf("\n");

    printf("\n🔹 Deleting 1 (leaf node)\n");
    root = delete(1, root);

    printf("Inorder after delete(1): ");
    inorder(root);
    printf("\n");

    printf("\n🔹 Deleting 2 (node with one child)\n");
    root = delete(2, root);

    printf("Inorder after delete(2): ");
    inorder(root);
    printf("\n");

    return 0;
}