Segmentation fault when using if statement with pointers (BST tree)

366 views Asked by At

I'm trying to implement a binary search tree in C, more specifically looking for the predecessor. However, whenever I try to run the program I get the segmentation vault. Here's the code in question:

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

struct tree
{
    int a;
    tree *left;
    tree *right;
    tree *prev;
}*root=NULL;

tree *searchSpecific (tree *root, int val)
{
    tree *x=root;
    if (!x)
    {
        return NULL;
    }
    else
    {
        while(x && val!=x->a)
        {
            if (val>x->a)
                x=x->left;
            else x=x->right;
        }
    }
    return x;
}

int previous(tree *root, int f)
{
 tree *x=searchSpecific(root,f);
    if(x->left)
    {
        x=x->left;
        while(x->right) x = x->right;
        return x->a;
    }

    tree *temp;
    do
    {
        temp = x;
        x = x->prev;
    } while(x && (x->right != temp));
    return x->a;
}

The segfault appears at the if statement if(x->left) in the previous() function. I want to check if the node in question exists, but the program crashes every time and I have no idea what is wrong with it..

2

There are 2 answers

2
Mureinik On BEST ANSWER

Since searchSpecific may return NULL, you need to protect your code from it, and check x before accessing one of its members:

tree *x=searchSpecific(root,f);
if (x != NULL && x->left)
1
Arial On

The segmentation fault can appear due to several reasons, such as:

  • x is undefined, which may be caused by your *searchSpecific function
  • x is NULL, because your function returns a NULL pointer
  • x->left is NULL, which means trying to access it causes something bad to happen

So, how I'll go about doing this would be trying to check if the returned tree is null using a simple if statement as follows:

if (x == NULL) {
    /* throw error or not found message */
}

I would also suggest you dynamically allocate memory for your tree before doing anything with it, by creating a reusable func like create_tree() with the following code:

tree create_tree(int data) {
    tree *x;
    x = malloc(sizeof(tree));
    x->a = data;
    x->left = x->right = x->prev = NULL;
    return x;
}

Why? Note that in your code snippets, you just declare

 tree *some_tree_name;

which is very dangerous every time you try to do something with it, and might lead to your code crashing on you on the do/while loop later.