CODEWITHSUNDEEP
csearchrecursionbinary-search-tree
rcj
rcj

Reputation: 661

recursively searching bst for non-key value

I'm having trouble with the logic of this. How do I search the entire tree (since I can't rely on any order search) and only return one matching value (if it exists)? If I return the recursive call, won't it fail once it hits the first leaf and hasn't found a match?

When using the function below, calls are made until a match is found or the end of the tree is reached, and the left-most node is returned regardless of matches.

My recursive function, traversing in-order:

tnode *find(tnode *ptr, const char *str)
{
    if (ptr == NULL) return ;

    if(strcmp (str,ptr->str) == 0)
        return ptr;


    else 
    {
        //search left subtree
        if (ptr->left != NULL)
            find(ptr->left, str) ;


        // search right subtree
        if (ptr->right != NULL)
            find(ptr->right, str) ;
    }

   return;

}

Upvotes: 0

Views: 170

Answers (2)

Useless
Useless

Reputation: 67852

If the left-subtree find returns non-NULL, you have a match and should return it. Currently you don't even look to see if it found anything.

If it didn't find anything, you can return the result of the right-subtree find (if it's NULL, you looked everywhere and didn't find anything).

tnode *find(tnode *ptr, const char *str)
{
    ptr *found;

    if (ptr == NULL) return NULL; /* nothing to see here */

    if(strcmp (str,ptr->str) == 0)
        return ptr; /* it is here! */

    /* try left subtree */
    found = find(ptr->left, str);
    if (found) return found; /* it was on the left */

    /* try right subtree */
    return find(ptr->right, str);
}

Upvotes: 1

Alex
Alex

Reputation: 10136

The first:

if (ptr == NULL) return ;

You supposed to return a value according to the function prototype (tnode *find(tnode *ptr, const char *str)).

The second:

find(ptr->right, str);

You do not use the return value, so anyway result will be incorrect.

The third:

return;

The same as the first.

If you will fix all of it, it supposed to work.

BTW if (ptr->left != NULL) is not necessary, as you are checking ptr == 0 at the beginning of the function.

The last one please pay attention to compiler warnings.

Upvotes: 2

Related Questions