CODEWITHSUNDEEP
crecursion
aquatorrent
aquatorrent

Reputation: 841

C: binary tree searching method


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 :(

Upvotes: 1

Views: 10263

Answers (4)

Fred Foo
Fred Foo

Reputation: 363507

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) ?:.

Upvotes: 4

babno
babno

Reputation: 309

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.

Upvotes: 0

Tim Lesher
Tim Lesher

Reputation: 6441

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;
}

Upvotes: 1

dwalter
dwalter

Reputation: 7468

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;
}

Upvotes: 1

Related Questions