CODEWITHSUNDEEP
c++recursionnodes
Kristers
Kristers

Reputation: 37

Recursive search in binary tree

I am a beginner and i am stuck on a function that searches unordered binary tree for given key. Node consists of value and pointers to left and right node. Here is my code:

node *btree::search(int key, node *leaf){
    if(leaf != NULL)
    {
        if(key == leaf->value)
        {
            return leaf;
        }
        search(key, leaf->left);
        search(key, leaf->right);

    }
    else
    {
        return NULL;
    }
}

node *btree::search(int key){
    return search(key, root);
}

In some cases my function returns the correct node, but in other it is runtime error. What is wrong with this and what could be done to fix this? And i am not allowed to use any external libraries like queue or others.

Upvotes: 1

Views: 1223

Answers (2)

Stephan Lechner
Stephan Lechner

Reputation: 35164

You invoke undefined behaviour, since not all code paths of your recursive functions return a value. This may result in a "runtime error", a crash, or simply some unpredictable result.

By the way, a search tree's advantage is usually that you get an average access time to your elements with runtime complexity n*log(n). But for that the tree must be ordered, and I cannot imagine a valid use case for an unordered binary tree; in this cases, a linked list would do the job as well.

In case of an ordered tree:

node *btree::search(int key, node *leaf){
    if(leaf != NULL)
    {
        if(key == leaf->value) {
            return leaf;
        } else if (key < leaf->value) {
            return search(key, leaf->left);
        } else {
            return search(key, leaf->right);
        }
    }
    else
    {
        return NULL;
    }
}

In case of an unordered tree:

node *btree::search(int key, node *leaf){
    if(leaf != NULL)
    {
        if(key == leaf->value) {
            return leaf;
        }
        leaf = search(key, leaf->left);
        if (! leaf) {
          leaf = search(key, leaf->right);
        }
        return leaf;
    }
    else
    {
        return NULL;
    }
}

Upvotes: 0

john
john

Reputation: 88092

It's quite a common beginner mistake. Your recursive function returns a node pointer, but when you make the recursive calls you ignore the return value. 

    search(key, leaf->left);
    search(key, leaf->right);

It should look like this

    node* ptr = search(key, leaf->left);
    if (ptr != NULL)
        return ptr;
    else
        return search(key, leaf->right);

I.e. return the node found by searching in the left sub-tree, but if that is NULL then search the right sub-tree and return the node found there (if any).

When you are writing recursive code you have to not only think about the recursive calls but also what's coming back from the recursive calls.

Upvotes: 1

Related Questions