Searching BST element function in C

Question

i think this must be simple problem, but i don't know what's wrong..

gdb says

Program received signal SIGSEGV, Segmentation fault.
0x000055555555543e in searchNode (root=0x0, X=1) at problem1.c:40
40      while(cursor->value != X || cursor != NULL)

insertion and searching function

typedef struct TreeNode
{
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
}   tree;

tree *insert(tree *root, int X)
{
    tree *cursor = root;
    tree *parent;

    while(cursor != NULL)
    {
        parent = cursor;
        if(X >= cursor->value)
            cursor = cursor->right;
        else
            cursor = cursor->left;
    }
    cursor = (tree *)malloc(sizeof(tree));
    cursor->value = X;
    cursor->left = cursor->right = NULL;
    cursor->parent = parent;
        return cursor;  
}

tree *searchNode(tree *root, int X)
{
    tree *cursor = root;

    while(cursor->value != X || cursor != NULL)
    {
        if(X >= cursor->value)
            cursor = cursor->right;
        else
            cursor = cursor->left;
    }

    if(cursor == NULL)
        return NULL;

    else if(cursor->value == X)
        return cursor;
}

main function

int main()
{
    tree *root = (tree *)malloc(sizeof(tree));
    root = NULL;

    insert(root, 10);
    insert(root ,20);
    insert(root, 5);
    insert(root, 1);
    insert(root, 15);
    insert(root, 20);
    insert(root, 30);
    insert(root, 100);
    insert(root, 40);
    insert(root, 50);

    node = searchNode(root, 1);
}

As far as i know, segmentation error mostly comes out when i reference NULL pointer, but i don't think search function is wrong. I think i made mistakes in insertion function or initializing tree root, but i don't know what's wrong..

GDB kindly tells you at which line there is a problem. Nothing prevents you from inspecting the contents of your variables in GDB. Follow some GDb tutorial, there must be tons of them — Jabberwocky, Oct 16 '18 at 13:42

Scheff's Cat · Accepted Answer · 2018-10-16T13:50:42.927

Out of curiosity, I looked into the code.

i don't think searching function is wrong

I don't agree!

Look at this line of code:

while(cursor->value != X || cursor != NULL)

What happens if cursor is NULL? cursor->value is accessed which is Undefined Behavior (because accessing NULL is not allowed). This is worth a Segmentation fault.

Better would be:

while (cursor != NULL && cursor->value != X)

or shorter:

while (cursor && cursor->value != X)

Recalling OP's snippet from gdb

Program received signal SIGSEGV, Segmentation fault.
0x000055555555543e in searchNode (root=0x0, X=1) at problem1.c:40
40      while(cursor->value != X || cursor != NULL)

(which I didn't realize on the first glance) this sounds very reasonable to me.

According to (root = 0x0), searchNode() seems to be called for an empty tree (root is NULL). Hence, tree *cursor = root; initializes cursor with a NULL pointer (and the rest above).

Thank you for your fast reply. i must be confused concept of OR and AND.. — lemoncake, Oct 16 '18 at 13:51
@신현섭 Yeah. And the order of arguments of `&&` is important as well. `&&` and `||` are [short-circuit](https://en.wikipedia.org/wiki/Short-circuit_evaluation). I.e. if first argument of `&&` evaluates to false second is not evaluated. That's why it works in the order I suggested. — Scheff's Cat, Oct 16 '18 at 13:53

score 0 · Answer 2 · answered Oct 16 '18 at 14:26

The problem with your insert function, is that it has no means of updating the value of root. You return the new leaf node, but that isn't of much use to you in tracking what root might be.

To be able to change root you have to pass in a pointer to it, like for example:

insert(&root, 10);

And then you could change your function like this. It traverses down the tree, passing in a pointer to the left or right branch of the current node until it finds that the node doesn't exist yet and then it creates it.

tree *insert(tree **root, int X)
{
    if(*root == NULL)
    {
        *root = (tree *)malloc(sizeof(tree));
        (*root)->value = X;
        (*root)->left = (*root)->right = (*root)->parent = NULL;
        return(*root);
    }
    else
    {
        tree *ret;
        if(X >= (*root)->value)
        {
            ret=insert(&(*root)->right, X);
            (*root)->right->parent=*root;
        }
        else
        {
            ret=insert(&(*root)->left, X);
            (*root)->left->parent=*root;
        }
        return ret;
    }
}

So the first time you call it, it'll populate root for you. The second time, it will pass in the pointer to root->right which will become the new root in your insert function and since that is NULL, it'll be created. And then for completeness sake it updates the parent linkage.

Searching BST element function in C

2 Answers2