how to create a c++ recursive function to return a node custom object?

Question

how are you?

I created a C++ recursive function in order to iterate over a binary tree and print out all the NODEs where the property COMPLETED = TRUE;

It´s working pretty fine because the type of the function is VOID and I am only printing out the result.

This is the way that works fine:

void findAndPrintFirstCompletedNodes(treeNode *lastNode) {
     if (lastNode == 0){
         return;
     }
     
   if (lastNode->completed == true) {
          cout << lastNode->word.morseWordElement << endl;
   
   }
      findAndPrintFirstCompletedNodes(lastNode->left);
      findAndPrintFirstCompletedNodes(lastNode->right);
   
 }

But what I want to do is to return the first found "COMPLETED" node instead of just printing!

I tried this way but is not working:

treeNode * findAndPrintFirstCompletedNodes(treeNode *lastNode) {
      if (lastNode == 0){
          return 0;
      }
      
    if (lastNode->completed == true) {
           return lastNode;
    
    }
       findAndPrintFirstCompletedNodes(lastNode->left);
       findAndPrintFirstCompletedNodes(lastNode->right);
    
  }

Thanks for the help.

Filipe

Answer 1

You seem not to be familiar how returning values works. The result of the lines

findAndPrintFirstCompletedNodes(lastNode->left);
findAndPrintFirstCompletedNodes(lastNode->right);

is ignored in your code. Only in the case that the input in the first recursion is completed, anything is returned. Frankly, I wonder why your compiler hasn't warned you.

I think your mistake is that you assume that a return in a recursive call would cause the original call to also return. It doesn't. It produces a value, which is then ignored.
Look at the code below:

int four()
{
    return 4;
}

int three()
{
    four();

    return 3;
}

What happens in here when you call three() is that an integer of value 4 is created, then thrown away, and then the value 3 is returned. three() does not return 4.

Try this:

treeNode * findAndPrintFirstCompletedNodes(treeNode *lastNode) {
    if (lastNode == 0){
        return 0;
    }
  
    if (lastNode->completed == true) {
        return lastNode;
    }

   treeNode* node;

   node = findAndPrintFirstCompletedNodes(lastNode->left);
   if(node) return node;

   node = findAndPrintFirstCompletedNodes(lastNode->right);
   if(node) return node;

   return nullptr;
}

In here, I store the return value of the recursive calls in the variable node, and return it in case it is not a null pointer, using null pointers as "not found".
In case neither the current node was complete nor anything was found in the recursive calls, I consequently return a null pointer.

You can shorten this to

treeNode* node;

node = findAndPrintFirstCompletedNodes(lastNode->left);
if(node) return node;

node = findAndPrintFirstCompletedNodes(lastNode->right);
return node;

or even

treeNode* node = findAndPrintFirstCompletedNodes(lastNode->left);
if(node) return node;

return findAndPrintFirstCompletedNodes(lastNode->right);

but I went with the version above because it should illustrate the point better.

---

By the way, I'd recommend that instead of

    if (lastNode == 0){
        return 0;
    }

you go with

    if (not lastNode){
        return nullptr;
    }

or

    if (lastNode == nullptr){

in order to make clear that we work with pointers.