what is wrong in my C++ code? Least Common ancestor

Question

To begin with I'm not new to C or C++. However, I'm currently working with C++ on Mac Yosemite. I'm just trying to write a recursive function to return the common ancestors of two nodes, that are identified by their key (data) variable. The logic is simple, traverse the tree until both the nodes are in the same branch, the node where these nodes diverge is the common ancestor. With this mind, I came up with the following code:

Node * commonAncestor(Node *n, int left_elem, int right_elem)
{
    if (n == NULL || n->key()==left_elem || n->key() == right_elem){return NULL;}
    if (left_elem < n->key() && right_elem > n->key()) {return n;}
    if (left_elem > n->key() || right_elem < n->key()) {
        cout<<"\n...Consider changing the order of the elements"<<endl;
    }
    if (left_elem < n->key() && right_elem < n->key()) {
        commonAncestor(n->Left(), left_elem, right_elem);
    }
    if (left_elem > n->key() && right_elem > n->key()) {
        commonAncestor(n->Right(), left_elem, right_elem);
    }
}

I should work, I have done similar programs. However, the program doesn't compile. I'm getting compiler error "control may reach end of non-void function" This is strange, as I have return statements. Also, to avoid this error I tried adding a return statement at the end, which only returned the root node. I'm confused... Should I do something with the XCode settings? Is my logic wrong?

Answer 1

This is because the returns are always inside IF statements so they could be not called... So the solution should be calling return also at the end of the function if it does go inside any IF (with NULL or the value you want).

Answer 2

That's because you forgot to return the value returned by your recursive calls. And also add a return NULL at the end, since compiler doesn't necessarily know that the end of the function is unreachable.

Node * commonAncestor(Node *n, int left_elem, int right_elem)
{
    if (n == NULL || n->key()==left_elem || n->key() == right_elem){return NULL;}
    if (left_elem < n->key() && right_elem > n->key()) {return n;}
    if (left_elem > n->key() || right_elem < n->key()) {
        cout<<"\n...Consider changing the order of the elements"<<endl;
        return NULL;
    }
    if (left_elem < n->key() && right_elem < n->key()) {
        return commonAncestor(n->Left(), left_elem, right_elem);
    }
    if (left_elem > n->key() && right_elem > n->key()) {
        return commonAncestor(n->Right(), left_elem, right_elem);
    }

    return NULL;
}

Answer 3

The compiler won't be happy unless it is certain something will be returned no matter what (even if your if's take care of all possible scenarios. At the end, where you presume your code will never reach, just throw a return NULL; and it will be happy.

Also, I may be wrong, but I believe you also want to return the result of recursively calling commonAncestor in your last two ifs.