CODEWITHSUNDEEP
csegmentation-faultbinary-search-tree
Shubham Gupta
Shubham Gupta

Reputation: 53

Segmentation Fault (Core dumped) in c BST

Here I have made a program for deletion in binary search tree(BST), but getting segmentation fault (core dumped) while executing, I think it's in delete function but where don't know if I remove function call for delete function then it works fine, like finding maximum element, inorder traversal, but delete won't work.

#include<stdio.h>
#include<stdlib.h>
struct BST{
    int data;
    struct BST *left;
    struct BST *right;
};
struct BST *newNode(int data){
    struct BST *temp = (struct BST *)malloc(sizeof(struct BST));
    temp->data=data;
    temp->left=0;
    temp->right=0;
    return temp;
}
void inOrder(struct BST *root){
    if(root==0)
        return;
    inOrder(root->left);
    printf("%d",root->data);
    inOrder(root->right);
}
struct BST *findMax(struct BST *root){
    if(root==0)
        return 0;
    if(root->right!=0)
        return findMax(root->right);
    return root;
}
struct BST *dele(struct BST *root,int data){
    if(root==0)
        return 0;
    if(data<root->data)
        root->left=dele(root->left,data);
    if(data>root->data)
        root->right=dele(root->right,data);
    else{
        if(root->left && root->right)
        {
            struct BST *temp=findMax(root->left);
            root->data=temp->data;
            root->left=dele(root->left,root->data);
        }
        else{
            struct BST *temp=root;
            if(root->left==0)
                root=root->right;
            if(root->right==0)
                root=root->left;
            free(temp);
            return root;
        }
    }
    return root;
}
void main(){
    struct BST *root = (struct BST*)malloc(sizeof(struct BST));
    root=newNode(1);
    root->left=newNode(2);
    root->right=newNode(3);
    root->left->left= newNode(4);
    root->left->right=newNode(5);
    root->right->left=newNode(6);
    root->right->right=newNode(7);
    inOrder(root);
    root=dele(root,1);
    printf("\n\n");
    inOrder(root);
}

Upvotes: 0

Views: 569

Answers (3)

David Ranieri
David Ranieri

Reputation: 41017

void main(){

please, change to:

int main(void) {

and use NULL instead of 0 to compare pointers

My debugger tells me:

Program received signal SIGSEGV, Segmentation fault. 0x00000000004007f0 in delete (root=0x0, data=5) at demo.c:47 47
if(root->right==0)

Steps for debugging (using gdb):

  • Compile using -g flag:

    gcc -std=c99 -pedantic -Wall -Wextra -W -g -o demo demo.c

  • Launch gdb:

    gdb demo

  • Type:

    run

Upvotes: 5

Shubham Gupta
Shubham Gupta

Reputation: 53

Corrected it myself, problem in delete function in else part

else if(root->data==data){
        if(root->left && root->right)
        {
            struct BST *temp=findMax(root->left);
            root->data=temp->data;
            root->left=dele1(root->left,root->data);
        }
        else{
            struct BST *temp=root;
            if(root->left==0)
                root=root->right;
            else if(root->right==0)
                root=root->left;
            free(temp);
            return root;
        }
    }

and nodes value i entered were not representing a BST, instead representing binary tree. So, changed it too.

root=newNode(5);
    root->left=newNode(3);
    root->right=newNode(7);
    root->left->left= newNode(1);
    root->left->right=newNode(4);
    root->right->left=newNode(6);
    root->right->right=newNode(8);

the segmentation fault was recovered by

else if(root->right==0

and, @Alter we can use both 0 as well as NULL, and as you told to change 

if (root->left==0)
        root=root->right;
    if (root->right==0)
        root=root->left;

which is correct but instead of second 'if' i should have used 'else if'. But thank for your interest in my question.

Upvotes: 1

rslemos
rslemos

Reputation: 2730

The culprit is

        if(root->left==0)
            root=root->right;
        if(root->right==0)
            root=root->left;

Consider the case where both left and right branches are NULL. Then the first if (tests whether left is NULL, which is) will assign NULL (right) to root. Then comes the next if and try to dereference a NULL pointer (root->).

I think the following will correct this bug

        if(root->left==0)
            root=root->right;
        else if(root->right==0)
            root=root->left;

Or: (edited: no, it will not work without else anyway, since the new right can be non NULL)

        if(root->left != NULL)
            root=root->left;
        if(root->right != NULL)
            root=root->right;

(note in this case that left and right cannot be possibly both non NULL, as this case was dealt with before, so no memory leak here).

Upvotes: 2

Related Questions