CODEWITHSUNDEEP
c++
Anurag Bharadwaj
Anurag Bharadwaj

Reputation: 11

Error in search function of binary search tree

struct node *search(struct node *root, int x)
{
    if(root->key == x || root == NULL)
    {
        return root;
    }   
    if(x < root->key)
    {
        return search(root->left, x);
    }
    else
    {
        return search(root->right, x);
    }
}

I am getting a segmentation fault when I search for an element not in the binary search tree.. What's wrong?

Upvotes: 1

Views: 40

Answers (1)

Jashaszun
Jashaszun

Reputation: 9270

Switch root->key == x and root == NULL to take advantage of short-circuiting in the || operator. You want to check that it is not null, and only then try to get properties from it.

Right now, what happens when you get to a search on a node that has no children? You either get search(root->left, x); or search(root->right, x);, both of which are equivalent to search(NULL, x);.

At that point, the first if statement becomes if (NULL->key == x || NULL == NULL). NULL->key is a dereference on the null pointer, which causes a seg-fault.

Upvotes: 2

Related Questions