C: binary tree searching method

Question

I'm trying to make a search method using a binary tree(no, it's not a binary search tree, just a binary tree) using a recursive function. If the data is on the binary tree, i want it to return the node and if it is not, i want it to return a NULL value. I have made the search function and it's doing its job perfectly. But the problem is, it seems that the function won't return the node.

Here's the struct for the binary tree:

struct data
{
    int number;
    struct data *left, *right;
}*root = NULL;

and this is the search function i'm talking about:

data* search(struct data *node, int key)
{
    if(node == NULL)
        return NULL;
    else
    {
        printf("\n%d %d -", node->number, key);

        if(node->number== key)
            return node;

        search(node->left, key);
        search(node->right, key);
    }
}

When i'm calling the search function like this: search(root, 6); , it says that it's returning a NULL value although i have pushed a 6 number into the binary tree(and the search function stops right at the return node; line too, so i'm assuming that the function is returning a NULL.)

I have seen a tutorial for binary tree in here , used and changed some code from it, but it's still the same. i'm desperately looking for help right here :(

When some invocation returns a non-null pointer, what happens to that value? — Jerry Coffin
– Jerry Coffin, Commented May 15, 2012 at 13:59
@KonradRudolph: actually it's C, but i'm using a C++ compiler, so, i think it won't be a problem . . — aquatorrent
– aquatorrent, Commented May 15, 2012 at 14:05
@Jerry Coffin: i'm not sure if i'm answering this right, but when it's not returning a non-null value, i want to push another data to the tree. — aquatorrent
– aquatorrent, Commented May 15, 2012 at 14:07
@aquatorrent It might not be a problem but that’s not why I asked. Rather, a good C++ solution would look completely different, and hence good advice should take this into account. — Konrad Rudolph
– Konrad Rudolph, Commented May 15, 2012 at 14:10

Fred Foo · Accepted Answer · 2012-05-15 14:18:20Z

4

~~Your function will always return NULL, except when the top node contains the key.~~ Your function does not do anything with the results from its recursive invocations; in fact, control flow may "fall off the end" of it without hitting a return statement.

You should check the return values from the recursive invocations and pass those up when appropriate:

if (node == NULL)
    return NULL;
else if (node->number == key)
    return node;
else {
    data *left = search(node->left, key);
    return left? left: search(node->right, key);
}

Note the "ternary operator" (if-then-else expression) ?:.

edited May 15, 2012 at 14:18

answered May 15, 2012 at 13:58

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Jerry Coffin Over a year ago

Sorry, but -1. When control flows off the end of the function after the recursive calls, you can't depend on it returning NULL (or anything else in particular).

Fred Foo Over a year ago

@JerryCoffin: it won't. The return values of the recursive calls are used in a return statement.

Tim Lesher Over a year ago

It's not running off the end--it's always returning one of three cases: NULL if node == NULL, node if node->number == key, and (data* || data*) in the third case. If the first search returns non-NULL, its value is used; if the second search returns non-NULL, its value is used; otherwise, it returns (data*)(0||0), which happens to be NULL.

Jerry Coffin Over a year ago

@larsmans: I'm not talking about your function (which is fine) but your statement that "Your function will always return NULL..." In his function, after the recursive calls, control flows off the end without returning any value. The precise result of that is (if memory serves) different between C and C++, but you certainly can't depend on it being NULL.

Fred Foo Over a year ago

@JerryCoffin: you're right, hadn't spotted that. Fixed it now.

|

dwalter · Accepted Answer · 2012-05-15 13:59:35Z

1

it will not return the searched node unless you use the return value of you search

change it to something like this.

data* search(struct data *node, int key)
{
  if(node == NULL)
    return NULL;
  else
  {
    printf("\n%d %d -", node->number, key);

    if(node->number== key)
        return node;
    struct data *tmp;
    tmp = search(node->left, key);
    /* node found ? */
    if (tmp)
        return tmp;
    tmp = search(node->right, key);
    /* node found ? */
    if (tmp)
        return tmp;
  }
  /* search didn't find anything */
  return NULL;
}

answered May 15, 2012 at 13:59

dwalter

7,5581 gold badge35 silver badges35 bronze badges

Comments

Tim Lesher · Accepted Answer · 2012-05-15 14:00:26Z

1

You're never actually returning the result from the recursive calls to search.

You need to check the return value from those calls, and if they found the node, return it

data* search(struct data *node, int key)
{
    data* found = NULL;

    if(node == NULL)
        return NULL;

    printf("\n%d %d -", node->number, key);

    if(node->number== key)
        return node;

    found = search(node->left, key);
    if (found)
        return found;

    found = search(node->right, key);
    if (found)
       return found;

    return NULL;
}

answered May 15, 2012 at 14:00

Tim Lesher

6,4702 gold badges31 silver badges42 bronze badges

Comments

babno · Accepted Answer · 2012-05-15 14:08:07Z

0

There is a much easier and more efficient way to make a binary tree, and that's simply with a vector/array.

i is the int to access your vector. To go right, i=i*2. to go left, i=i*2+1. They will never share a same spot and assuming equal distribution each spot will be taken.

answered May 15, 2012 at 14:08

babno

3092 gold badges7 silver badges16 bronze badges

Collectives™ on Stack Overflow

C: binary tree searching method

4 Answers 4

7 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

7 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related