CODEWITHSUNDEEP
c++pointersrecursionbinary-search-treereturn-value
user3002386
user3002386

Reputation: 125

C++ recursive function return value

As a homework, I am implementing a binary search tree, and was doing the part of searching for a position of some data (to be able to modify/remove it later), here is my piece of code:

node*& bst::search(data& x, node*& pos) {
    if (pos->get().num == x.num) {
        return pos;
    }
    if (pos->right != NULL) search(x, pos->right);
    if (pos->left != NULL) search(x, pos->left);
}

In the source file I call search(data_to_find, root). In my example I had a tree of integers of this form:

1
 2
  3

with the root pointing to 1. When I wanted to search for element 3, I was expecting to get the pointer to 3, but every single time this function returns the root itself. Then I thought maybe this had to do with the first instance of foo not returning a value, so I changed search(x, pos->right) to return search(x, pos->right) and same for left, and this time everything worked OK. This made me confused, I tried to do a few runs with the following dummy function just to understand what would it return

int foo(int x = 0) {
    if (x == 1) {
        return x;
    }
    x++;
    foo(x);
}

Although I haven't specified what to return in case the if statement is false, it stills works and outputs 1. I thought maybe foo(0) just returned whatever foo(1) returned in the recursion, to check that I tried this:

int boo() {
    return 1;
}

int foo() {
    boo();
}

and called foo(), which resulted in a "foo must return a value" error, obviously changing boo() to return boo() fixed it. Sooo my question is why is the first case outputting root? And why is the second case even working?

Upvotes: 1

Views: 1701

Answers (1)

Mikel F
Mikel F

Reputation: 3656

The problem you have here is that you do not propagate the return value of your recursive calls back to the original caller. As it is, when those calls return, the value is discarded.

Even worse, in cases where you don't find your match, you function as written fails to return anything, which is undefined behavior. The fact that you get the root node is more a quirk of the compiler or your current memory layout rather than a defined result.

As was pointed out by @Mike, for a binary tree, you should only be traversing one sub-tree in a search, based on whether or not your search value is greater or less than the value held by the current node. Traditionally, the left tree holds values smaller than the current node, while the right tree holds values that are greater.

Upvotes: 3

Related Questions