Understanding the Functionality of a Binary Tree Implementation in C

I am having trouble with the delete function to remove a node from a binary tree. This is my first tree program and I find the books and internet pages very confusing for the delete function. I wrote some code for this, but it does not delete the node. I would appreciate your help.


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

typedef struct node{
    int data;
    struct node *left;
    struct node *right;
}node;

node *root=NULL;

node *getnode();
//void insert(node **tree, int val);
void insert(node *tree, int val, node *parent);
void inorder(node *tree);
void preorder(node *tree);
void postorder(node *tree);
void delete(node *tree, int val);
node *largestnode( node *tree);

int main (){
    int choice, val;
    while(1){
        printf("\n1. Insert\n2. Inorder\n3. Preorder\n4. Postorder\n5. Delete\n6. Exit\nEnter your choice: ");
        scanf("%d", &choice);
        switch(choice){
            case 1:
                printf("Enter the value to be inserted: ");
                scanf("%d", &val);
                if(root==NULL){
                    root=getnode();
                    root->data=val;
                }
                else{
                    insert(root, val, root);
                }
                break;
            case 2:
                inorder(root);
                break;
            case 3:
                preorder(root);
                break;
            case 4:
                postorder(root);
                break;
            case 5:
                printf("Enter the value to be deleted: ");
                scanf("%d", &val);
                delete(root, val);
                break;
            case 6:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}

node *getnode(){
    node *newnode = (node*)malloc(sizeof(node));
    newnode->left=newnode->right=NULL;
    return newnode;
}

void insert(node *tree, int val, node *parent){
    if(tree==NULL){
        tree=getnode();
        (tree)->data=val;
        if(parent->data>val){
            parent->left=tree;
        }
        else{
            parent->right=tree;
        }
    }
    else if (val<(tree)->data){
        parent=tree;
        insert(((tree)->left), val, parent);
    }
    else{
        parent=tree;
        insert(((tree)->right), val, parent);
    }
    
}

/*void insert(node **tree, int val){
    if(*tree==NULL){
        *tree=getnode();
        (*tree)->data=val;
    }
    else if (val<(*tree)->data){
        insert(&((*tree)->left), val);
    }
    else{
        insert(&((*tree)->right), val);
    }
}*/

void inorder(node *tree){
    if(tree != NULL){
        inorder(tree->left);
        printf("%d\t", tree->data);
        inorder(tree->right);
    }
}

void preorder(node *tree){
    if(tree != NULL){
        printf("%d\t", tree->data);
        preorder(tree->left);
        preorder(tree->right);
    }
}

void postorder(node *tree){
    if(tree != NULL){
        postorder(tree->left);
        postorder(tree->right);
        printf("%d\t", tree->data);
    }
}
    
void delete(node *tree, int val){
    node *temp;
    if(tree==NULL){
        printf("Element not found\n");
    }
    else if(val<tree->data){
        delete(tree->left, val);
    }
    else if(val>tree->data){
        delete(tree->right, val);
    }
    else{
        if(tree->left && tree->right){
            temp=largestnode(tree->left);
            tree->data=temp->data;
            delete(tree->left, temp->data);
        }
        else{
            temp=tree;
            if(tree->left==NULL){
                tree=tree->right;
            }
            else if(tree->right==NULL){
                tree=tree->left;
            }
            free(temp);
        }
    }
}

node *largestnode( node *tree){
    if(tree==NULL) return NULL;
    else if(tree->right==NULL) return tree;
    else return largestnode(tree->right);
}

ignore the comment I wrote it as an alternate way for the insert function.

I tried to write a function that would delete a node from a binary tree by finding the node, replacing it with its successor, and then freeing the memory. I expected the function to remove the node from the tree and update the tree structure. But it didn't go as planned.I think there is something wrong with my logic or pointer operations.

Solution

If you delete the root node then the caller needs to know what the new root node is. You can either return it (see below), or pass in a node **tree to update it.

The only tricky case is deleting the root node when it has both a left and right child. In that case you find the smallest leaf node in the right tree next (or equivalent as you had it the largest leaf node in the left tree) and along with its parent next_parent. Overwrite the root's data with the leaf data then patch up up the hole left by the leaf when you subsequently delete the leaf node:

node *delete(node *tree, int data) {
    if(!tree) {
        printf("Element not found\n");
        return tree;
    }
    if(tree->data > data) {
        tree->left = delete(tree->left, data);
        return tree;
    }
    if(tree->data < data) {
        tree->right = delete(tree->right, data);
        return tree;
    }
    if(!tree->left) {
        node *temp=tree->right;
        free(tree);
        return temp;
    }
    if(!tree->right) {
        node *temp=tree->left;
        free(tree);
        return temp;
    }
    struct node *next_parent = tree;
    struct node *next = tree->right;
    for(; next->left; next = next->left, next_parent = next);
    if (next_parent == tree)
        next_parent->right = next->right;
    else
        next_parent->left = next->right;
    tree->data = next->data;
    free(next);
    return tree;
}

// ...

            case 5:
                printf("Enter the value to be deleted: ");
                scanf("%d", &val);
                root = delete(root, val);
                break;

and example run (I tweaked the program to only show the menu the first time just be shorter):

1. Insert
2. Inorder
3. Preorder
4. Postorder
5. Delete
6. Exit
Enter your choice: 1
Enter the value to be inserted: 0
Enter your choice: 1
Enter the value to be inserted: -1
Enter your choice: 1
Enter the value to be inserted: 3
Enter your choice: 1
Enter the value to be inserted: 4
Enter your choice: 2
-1       0     3    4
Enter your choice: 5 
Enter the value to be deleted: 0
Enter your choice: 2
-1       3     4