binary search tree node always NULL

Question

I know this may seem simple, but I have been scratching my head for the last few hours trying to figure out why whatever I do, thisNode is always NULL. Because this is null, it means that nothing actually ends up getting added to the tree. Does any have any ideas? Arghhh

struct node *tra(struct node * start, Type input) 
{
    struct node * thisNode = start;

    if (thisNode == NULL)
        return thisNode;
    else 
    {
        Type current = thisNode -> el;

        if (strcmp(input, current) > 0)
            return tra(thisNode -> right, input);
        else if (strcmp(input, current) < 0)
            return tra(thisNode -> left, input);
        else
        return thisNode;
    }
}

Ta insert(Type input, Ta ta) 
{
    if ((find(input, ta)) == FALSE) 
    {
        struct node *newEl = tra(ta -> head, input);
        newEl = (struct node*)malloc(sizeof(struct node));
        newEl -> el = input;
        newEl -> left = NULL;
        newEl -> right = NULL;
    }

    return ta;
}

Boolean find(Type input, Ta ta) 
{
    if (tra(ta -> head, input) == NULL)
        return FALSE;
    else
        return TRUE;
}

Asking people to spot errors in your code is not especially productive. You should use the debugger (or add print statements) to isolate the problem, and then construct a [minimal test-case](http://sscce.org). — Oliver Charlesworth, Feb 17 '13 at 22:43
@OliCharlesworth sorry I should've rephrased the question. I meant do you have any ideas how I can correct this? I've been using a debugger for the last few hours trying to figure this out. I know that it is NULL because it always enters the first if statement, but I simply cannot figure out why this is the case. — user1899174, Feb 17 '13 at 22:49
http://stackoverflow.com/q/14926949/905902 Is there any reason to repost the same question ? — wildplasser, Feb 17 '13 at 23:12
@wildplasser Umm... that's a link to this URL... Did you mean [this one](http://stackoverflow.com/questions/14922802/c-binary-search-tree-implementation-insert)? — Bernhard Barker, Feb 17 '13 at 23:13
@wildplasser I see that both of these issues are connected, and it seems that your way in the previous question was the right way to go about solving it. — user1899174, Feb 17 '13 at 23:16

score 1 · Answer 1 · answered Feb 17 '13 at 22:49

Here is the problem:

        struct node *newEl = tra(ta -> head, input);
        newEl = (struct node*)malloc(sizeof(struct node));

you allocate the new node, but then the pointer newEl get lost. Your function tra should return a pointer to the pointer, to let the insert function modify the node to which you attach the newly created node.

Bernhard Barker · Answer 2 · 2013-02-18T07:58:18.047

0

The problem is as follows:

When there's nothing in the BST, this triggers in tra:

if (thisNode == NULL)
    return thisNode;

So then newEl == NULL in insert.

Then you malloc to assign the pointer newEl a new value pointing to allocated memory. But the original pointer which you returned still has the value of NULL (because giving a copy of a pointer a new value doesn't change the original pointer).

Options for dealing with this:

Return a pointer to a pointer (struct node **) (and I think you'd also need to pass a pointer to a pointer as parameter to the insert function).
Change your check in tra to look at the next element (and appropriate changes). For a linked-list it would look like: if (thisNode->next == NULL) return thisNode; and in insert you'd work with newEl->next. While generally a good option for linked-lists, this is a bit more effort for BSTs, since you need to return whether the left or right nodes were NULL, or perform this check again in insert.
- Note - you'd have to work with either newEl->left or newEl->right in insert.
Return by reference - this is probably the easiest option. Change tra to return struct node *& and change newEl declaration to struct node *&newEl = ..., and that's probably about all.

edited Feb 18 '13 at 07:58

answered Feb 17 '13 at 22:53

Bernhard Barker

54,589
14
104
138

Ok so I've decided to go with the second option. But if i changed the check to `if (thisNode -> head == NULL)`, surely I don't need to make any changes in insert to workwith `newEl -> head`, because I have already return `newEl -> head` in `tra`? – user1899174 Feb 17 '13 at 22:59
Also, why would I need to check if `thisNode` has a `head` element? Surely the `tree` would have a head element? – user1899174 Feb 17 '13 at 23:05
I think I understand what you mean. Is there any way I can show you what I have done in order for you to see whether I am on the right track? – user1899174 Feb 17 '13 at 23:19
http://pastebin.com/pWq5Y3YF if you look at the traverse method, thats what I've understood from your explanation. Thanks a lot. – user1899174 Feb 17 '13 at 23:42
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/24676/discussion-between-user1899174-and-dukeling) – user1899174 Feb 17 '13 at 23:43

binary search tree node always NULL

2 Answers2