CODEWITHSUNDEEP
csearchbinary-tree
user2171983
user2171983

Reputation: 17

Search in Binary Tree (BT) Not BST

I am trying to do a search operation in BT. For example:

       3 (Root)
   5       1
 6   2    0  8

This is my BT and this is the code I have written for search.

Node* search(Node *root,int key)
{
    if(root)
    {
        if(root->key==key)
        {
            cout<<root->key<<endl;
            return root;
        }
        search(root->left,key);
        search(root->right,key);
    }
}

Its a pre-order traversal with the condition, that when I find my desired node, I should return it. For example if I call search(root,2) the search should return a Node* pointer to the node containing the value 2.

I believe when my code returns after the condition is met, it only returns to the outer call n doesn't exit out completely. For example if A Calls B Calls C, n then there is a return in C, it returns the value to B rather than to the function that called A.

I am not able to get my head around how to solve this. I am still quite new to recursion, so having a hard time visualizing things.

Any help appreciated !

Upvotes: 0

Views: 96

Answers (3)

Shubh
Shubh

Reputation: 81

Add exit function after the condition is met,to reduce overhead of the program.Also add a condition for not found

if(root->key==key)
    {
        cout<<root->key<<endl;
        return root;
        exit(-1); 
    }

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

Node* search(Node *root, int key){
    if(root){
        if(root->key == key){
            return root;
        }
        Node *ret;
        (ret = search(root->left, key)) || (ret = search(root->right, key));
        return ret;
    }
    return NULL;
}

Upvotes: 0

Colin Phipps
Colin Phipps

Reputation: 908

Issue 1: you need a return value when do not find the requested value. return NULL; at the end of your function.

Issue 2: when you recurse, you are delegating the job of finding the result to another function call - and you then need to return that result if it finds it. So you should do something like:

Node* r = search(root->right, key);
if (r) return r;

Upvotes: 1

Related Questions