CODEWITHSUNDEEP
c++if-statementrecursionbinary-tree
Scholar
Scholar

Reputation: 293

Why does this recursive function behave different than intended?

I am writing a binary tree and I am stuck on a search function that takes a value x and determines if it is a leaf in the tree or not.

Here is what I have:

bool search(Node<T>* &currentNode, const T& x) const
{
    /* Base Case */
    if ( currentNode != nullptr && (leaf(currentNode) == true) && currentNode->data == x )
    {
        return true;
    }

    /* Recursive Case */
    else {

        if (currentNode != nullptr)
        {
        search(currentNode->left, x);
        search(currentNode->right, x);
        }

        //If first if condition is not met for all values then value must not exist
        return false;

        }


bool leaf(Node<T>* currentNode) const 
{
    if (currentNode != nullptr)
    {
    return ((currentNode->left == nullptr && currentNode->right == nullptr) ? true : false);        
    }
    else  
    {
        return true;
    }
}

The code always returns false, why is the first IF statement never triggered?

EDIT: Code calling search:

for (int i = 0; i < 101; i++)           
            if ((t.search(i) == true) ? cout << "LEAF FOUND: " << i  << endl : cout << " NOT A LEAF: " << i << endl);

Upvotes: 0

Views: 83

Answers (2)

peanut-lord
peanut-lord

Reputation: 23

Because you don't return the boolean from the search method back:

if (currentNode != nullptr)
{
search(currentNode->left, x);
search(currentNode->right, x);
}

You always will return false.

Upvotes: 0

Ahmad Abo Bakr
Ahmad Abo Bakr

Reputation: 121

dealing with recursion can be tricky :D.

unless the root node is a leaf your code will always return return false your code returns true to the function that made the call not all the way back to the original caller ( before recursion)

let's say your tree had three elements and the item was in the left leaf so in the root node you called yourself with the left node so it returned true to the caller ( the root node) , the root node does nothing with this and just continue executing.

this can be simply solved simply by adding an if statement to check for the returned value of the functions you called

if (currentNode != nullptr)
{
    if(search(currentNode->left, x)) return true;
    if(search(currentNode->right, x)) return true;
}
return false;

Upvotes: 1

Related Questions