DeleteElement for Binary Search Tree is giving runtime error?

Question

I am trying to write a function called 'DeleteElement' for deleting an element in Binary Search Tree.It compiles properly but it is giving runtime error. Please help me debug the error. Thanks in advance.

C Code:

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


struct BinaryTree
{
         int data;
         struct BinaryTree *left;
         struct BinaryTree *right;
};


int FindMin(struct BinaryTree *root)
{
    if(root == NULL)
    {
        return NULL;
    }
    while(root->left)
    {
        root = root->left;
    }
return root->data;

}


int FindMax(struct BinaryTree *root)
{
    if(root == NULL)
    {
        return NULL;
    }
    while(root->right)
    {
        root = root->right;
    }
return root->data;
}



struct BinaryTree *DeleteElement(struct BinaryTree *root,int element)
{
    struct BinaryTree *temp;
    if(root == NULL)
    {
        printf("Element Not found");
        //return NULL;
    }
    else if(element > root->data)
    {
        root->right = DeleteElement(root->right,element);
    }
    else if(element < root->data)
    {
        root->left = DeleteElement(root->left,element);
    }
    else
    {
        if(root->left && root->right)
        {
            int temp1 = FindMax(root->left);
            root->data = temp1; 
            root->left = DeleteElement(root->left,root->data);
        }
        else 
        {
            temp = root;
            if(root->left == NULL)
            {
                root = root->right;
            }
            if(root->right == NULL)
            {
                root = root->left;
            }
            free(temp);
        }
    }
    return root;
}

int main()
{
    struct BinaryTree * root = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    root-> data = 7;
    struct BinaryTree * l = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    l -> data = 4;
    struct BinaryTree * ll = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    ll -> data = 2;
    ll -> left = ll -> right = NULL;
    struct BinaryTree * lr = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    lr -> data = 5;
    lr -> left = lr -> right = NULL;
    l -> left = ll;
    l -> right = lr;
    struct BinaryTree * r = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    r -> data = 9;
    struct BinaryTree * rl = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    rl -> data = 8;
    rl -> left = rl -> right = NULL;
    struct BinaryTree * rr = (struct BinaryTree *)malloc(sizeof(struct BinaryTree));
    rr -> data = 11;
    rr -> left = rr -> right = NULL;
    r -> left = rl;
    r -> right = rr;
    root -> left = l;
    root -> right = r;


    printf("Max %d\n",FindMax(root));
    printf("Min %d\n",FindMin(root));
    DeleteElement(root,2);
    printf("Max %d\n",FindMax(root));
    printf("Min %d\n",FindMin(root));
    return 0;
}

Answer 1

THE PROBLEM :

The problem resides in the following lines :

if(root->left == NULL)
{
  root = root->right;
}
if(root->right == NULL)
{
  root = root->left;
}

The first condition might be true and the program will change the value of root. But the second if statement will still be evaluated, and since root might have been changed to NULL in the previous statement there can be a runtime error. (Trying to access a field of NULL is never a good thing)

THE FIX :

You should change the second if by an else if like this :

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