Problem with Deleting node in BST (Binary Search Tree) function (code)

Question

We know that there is two ways to delete node if he had two childs in my exemple if we take the min of the maxs all is good when we take the max of the mins the program miss or remove a sub-tree of the node we remove. On my code please.

I tried to do pointer of pointer in the functions and nothing changes. I tried to do a pointer on the node we delete and do the process starting from it and still not working.

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

typedef struct noeud Node;
struct noeud
{
    int valeur;
    Node *gauche;
    Node *droit;
};

Node *createNode(int val)
{
    Node *newNode = malloc(sizeof(Node));
    newNode->valeur = val;
    newNode->gauche = NULL;
    newNode->droit = NULL;
    return newNode;
}

void infixe(Node *root)
{
    if (root == NULL)
        return;
    infixe(root->gauche);
    printf("%d - ",root->valeur);
    infixe(root->droit);
}

Node* findMin(Node* root){
    Node* current=root;
    while(current->gauche!=NULL)
        current=current->gauche;

    return current;
}
Node* findMax(Node* root){
    Node* current=root;
    while(current->droit!=NULL)
        current=current->droit;

    return current;
}

Node* deleteInBST(Node* root,int val){
     
    if(root==NULL) return root;

    if(val<root->valeur){
        root->gauche=deleteInBST(root->gauche,val);
    }
    else if(val>root->valeur){
        root->droit=deleteInBST(root->droit,val);
    }
    else{
            //! here of the root we wanna delete hasn't gauche child so we take the droit and we delete the root
            if(root->gauche==NULL){
                Node* temp=root->droit;
                free(root);
                return temp;
            }   
            //! here of the root we wanna delete hasn't droit child so we take the gauche and we delete the root
            else if(root->droit==NULL){
                Node* temp=root->gauche;
                free(root);
                return temp;
            }
            else{
            //! here if the root has two child so we have 02 ways to do it 
                //! the first we take the min of the maxs
                /*Node* temp=findMin(root->droit);
                root->valeur=temp->valeur;
                root->droit=deleteInBST(root->droit,temp->valeur);
                //! the second we take the max of the mins 
                */
                Node* temp=findMax(root->gauche);
                root->valeur=temp->valeur;
                root->gauche=deleteInBST(root->gauche,temp->valeur);
                
                return root;
            }
    }
}


int main(){ 
    
    Node* root = createNode(25);
    root->gauche = createNode(10);
    root->droit = createNode(60);
    root->gauche->gauche = createNode(5);
    root->gauche->droit = createNode(20);
    root->gauche->droit->gauche = createNode(15);
    

    root->droit->gauche = createNode(35);
    root->droit->gauche->gauche = createNode(30);
    root->droit->gauche->droit = createNode(45);

    
    root->droit->gauche->droit->gauche = createNode(40);
    root->droit->gauche->droit->gauche->gauche = createNode(37);
    root->droit->gauche->droit->gauche->droit = createNode(43);


    root->droit->droit = createNode(65);
    root->droit->droit->droit = createNode(70);



    printf("\n");
    infixe(root);

    /*//! here if we do root=deleteInBST(root,60) we lose the tree if we keep it like i wrote it we lose the sub_tree of 60 in the 
        // !most left           */

    deleteInBST(root,60);
    printf("\n");
    infixe(root);
    
    return 0;
}

Answer 1

The problem is that your recursive function doesn't always execute a return statement. Notably in the case where the node with value val has not yet been found, you don't return the root after the recursive call has been made.

The solution is to move the last return root; statement out of the two nested else blocks so that it is also executed in the cases where val is different from root->valeur.

Answer 2

You are missing return values in two important cases. You should be getting a compiler warning.

    if(val<root->valeur){
        root->gauche=deleteInBST(root->gauche,val);
        return root;
    }
    else if(val>root->valeur){
        root->droit=deleteInBST(root->droit,val);
        return root;
    }