binary tree recursively search c code [not Binary Search Tree]

Question

The problem with my code is that,when a left child value is searched then due do to recursion levels it goes back and checks the right child.And the return gets incorrect. I can't find a way to get past it.

node * search(node *ptr,int key)
{
    if(ptr->data==key)
        return ptr;
    else
    {
        if(ptr->lchild!='\0')
            search(ptr->lchild,key);
        else
            return '\0';
        if(ptr->rchild!='\0')
            search(ptr->rchild,key);
        else
            return '\0';
    }
}

Please give the declaration of `node`. And you may perhaps code `return search(ptr->lchild,key);` but I don't understand what your code wants to do. What kind of tree are you coding? How is the tree constructed? What are its invariants? — Basile Starynkevitch, Apr 21 '13 at 07:46
@BasileStarynkevitch It's just an unsorted binary tree. There is sufficient data about `node` — SomeWittyUsername, Apr 21 '13 at 07:59
@BasileStarynkevitch it's just a simple node with two child link pointers and an integer data....and it's unsorted cause it's just a binary tree...not an Binary Search Tree — Suman Mitra, Apr 21 '13 at 13:04

BLUEPIXY · Accepted Answer · 2013-04-21T08:52:10.760

4

Perhaps like this

node * search(node *ptr,int key)
{
    node *pwk;
    if(ptr == NULL) return NULL;
    if(ptr->data==key)
        return ptr;
    if(NULL!=(pwk=search(ptr->lchild,key)))
        return pwk;
    if(NULL!=(pwk=search(ptr->rchild,key)))// or return search(ptr->rchild,key);
        return pwk;
    return NULL;
}

edited Apr 21 '13 at 08:52

answered Apr 21 '13 at 07:53

BLUEPIXY

39,699
7
33
70

score 1 · Answer 2 · answered Apr 21 '13 at 07:52

That's right. Try this:

node * search(node *ptr,int key)
{
    if(ptr->data==key)
        return ptr;
    else
    {
        node *current = NULL;
        if(ptr->lchild != NULL)
            current = search(ptr->lchild,key);

        if(current == NULL) /* not found in the left subtree */
        {
            if(ptr->rchild != NULL)
                current = search(ptr->rchild,key);
        }
        return current;
    }
}

wildplasser · Answer 3 · 2013-04-21T17:01:25.397

1

Node *search(Node *ptr, int key)
{
    Node *found;
    if ( !ptr || ptr->data == key) return ptr;

    found = search(ptr->lchild, key);

    return (found) ? found : search(ptr->rchild, key);
}

Note: both || and ?: use the short circuit evaluation, which allows me to reduce the number of if(...) conditions to one.

UPDATE: If we are allowed to use the the "crippled ternary" operator gnu-extension, we can also avoid the variable:

Node *search2(Node *ptr, int key)
{
    if ( !ptr || ptr->data == key) return ptr;

    return search2(ptr->lchild, key) ?: search2(ptr->rchild, key);
}

Adding yet another ternary completely removes the if(...):

Node *search3(Node *ptr, int key)
{
    return ( !ptr || ptr->data == key) 
        ? ptr
        : search3(ptr->lchild, key) ?: search3(ptr->rchild, key);
}

edited Apr 21 '13 at 17:01

answered Apr 21 '13 at 11:26

wildplasser

43,142
8
66
109

Just wondering, why? Why working so hard to remove a perfectly valid if statement and end up with esoteric and non-portable "crippled ternary"? – SomeWittyUsername Apr 21 '13 at 16:44
The reason is simple: simplicity. Fewer {lines,variables} := less chance for error. And: I don't like extensions, either, but the example makes it clear that there is a case for the crippled ternary. It might even get included in the next C standard. – wildplasser Apr 21 '13 at 17:01
Simplicity != less code. This is pretty compact: `for(unsigned i = 0; i < 20; i++) a[i & (unsigned)(-2)] = i;` but totally unreadable and error-prone. – SomeWittyUsername Apr 21 '13 at 17:21
The other reason is verifiability. In my (and @BLUEPIXY 's) answer the function tests for ptr being NULL before doing anything else. Yours (and all others) checks for it in two places (before the recursive calls) but would still fail when called with a NULL ptr argument. – wildplasser Apr 21 '13 at 17:48
oh, please! That's lame. My answer doesn't pretend to be a masterpiece, it's just a sketch. My question to you was very specific and unrelated to nullity check – SomeWittyUsername Apr 21 '13 at 18:54

score 0 · Answer 4 · edited May 23 '17 at 10:25

node * search(node *ptr,int key)
{
    Node * p;

    // Found the key, return the pointer to the node
    if (ptr->data==key)
        return ptr;

    if (ptr->lchild != NULL)
    {
        p = search(ptr->lchild,key);
        // Found the key, return the pointer to the node
        if(p != NULL)
            return p;
    }
    // Didn't find it in the lchild, so search rchild
    if (ptr->rchild != NULL)
    {
        p = search(ptr->rchild,key);
        // Found the key, return the pointer to the node
        if(p != NULL)
            return p;
    }

    // Not found in left or right child, return NULL
    return NULL;
}

Avoid using \0 in this case. \0 is used for a null character. NULL is used for a null pointer. Though both are usually 0, it's preferable to use NULL for pointers. Check this question for more details - What is the difference between NULL, '\0' and 0

binary tree recursively search c code [not Binary Search Tree]

4 Answers4