Ensuring Recursive Functions With Multiple Returns "Preserve" Desired Results

Question

Consider this code (quoted from geeksforgeeks.org, author Tushar Roy) which calculates true or false if the path from a root to a leaf has keys that sum to a specified value:

bool hasPathSum(struct node* node, int sum)
{
  /* return true if we run out of tree and sum==0 */
  if (node == NULL)
  {
     return (sum == 0);
  }

  else
  {
    bool ans = 0; 

    /* otherwise check both subtrees */
    int subSum = sum - node->data;

    /* If we reach a leaf node and sum becomes 0 then return true*/
    if ( subSum == 0 && node->left == NULL && node->right == NULL )
      return 1;

    if(node->left)
      ans = ans || hasPathSum(node->left, subSum);
    if(node->right)
      ans = ans || hasPathSum(node->right, subSum);

    return ans;
  }
}

In this code, the author has used the logical OR operator in his assignments to a variable ans which he returns to avoid overwriting a return of true with a return of false. I have refactored the code into:

int hasPathSum(Treelink tree, int sum){
    if ( !tree ) { //succesful path found
        return (sum == 0);
    } else {
        sum -= tree->item;
        if ( (sum == 0) && (!tree->left && !tree->right)) 
            return 1;
        return hasPathSum(tree->left, sum) || hasPathSum(tree->right, sum);
    } 
}

Although it is obvious with this case that using a temporary variable and/or the logical OR operator are effective in preventing overwrites of recursive returns, what are some best methods for carrying a value up a recursive call?

EDIT

Conversely, let us consider a slightly contrived example; Given an improperly ordered binary tree (say, key 100 as root with left child's key as 5 and right child's key as 2), find the minimum key from the tree recursively. I would naively approach this as so:

Disclaimer: written but not compiled.

int findMin(Tree tree, int min) {
    if (!tree) return 0; //defensive check

    if ( tree->item < min && (tree->left || tree->right) ) { 
        //Can go deeper and reestablish the min in both directions
        if ( tree->left ) 
            min = findMin(tree->left, tree->item);
        if ( tree->right ) 
            min = findMin(tree->right, tree->item);
    } else if ( tree->item >= min && (tree->left || tree->right ) ) {
        //can go deeper but should not reestablish the min
        if ( tree->left ) 
            min = findMin(tree->left, min);
        if ( tree->right ) 
            min = findMin(tree->right, min);
    } else {
        return min; //return min's final value
    }
}

It would presumably be called via findMin(testTree, testTree->item). Fundamentally; we are forced to go down both branches from the root to explore and find a key that might be anywhere in the tree (even the root itself!) We know we have to make assignments to 'pull up' the right key, however this would most probably overwrite the 'true' min of the previous call (the way this is currently written) unless we did some kind of bounded check on each assignment e.g.

tmpmin = findMin(tree->left);
min = (min < tmpmin) ? min : tmpmin;  

We could also perhaps have two separate variables (as this is a binary tree, after all) that specify the left min and the right min and merely return the min of the two. In these cases I am still using some kind of temporary variables to piggy back to its original caller. Ultimately, I am curious about generic heuristics regarding avoiding these types of mistakes when designing recursive algorithms.

Answer 1

Here is the original example without optimization. You'll see that the algorithm is much cleaner now.

bool hasPathSum(struct node* node, int sum)
{
  /* return true if we run out of tree and sum==0 */
  if (node == NULL)
     return (sum == 0);

  /* otherwise check both subtrees */
  int subSum = sum - node->data;
  return hasPathSum(node->left, subSum) ||  hasPathSum(node->right, subSum);
}

With regards to the actual question - how to return values in this sort of recursion where there's no constraint on the data in the data structure. Returning the current minimum for the sub-tree (or whatever data structure you actually look at) works just fine.

Simply consider the problem without regarding the actual data structure.

current = useful_start_value
for value in data:
    if binaryOp(current, value):
       current = value   

So for every value you have to test it against the current data. For the findMin function this results in the following code. I've adapted to use the original data structures.

int findMin(struct node* node, int min) {
    if (!node) return min;
    if (node->data < min)
       min = node->data;

    int leftMin = findMin(node->left, min);
    if(leftMin < min)
       min = leftMin;

    int rightMin = findMin(node->right, min);
    if(rightMin < min)
       min = rightMin;

    return min;
}

As a side - written like this you can also see the actual order the nodes are visited cleanly.

My general advice would be:

• Don't optimize early (and badly)
• Do the recursive calls at exactly one position in the source code (if you can).
• Try to treat the problem as a local problem - as in findMin we just had to find the minimum of three values - so we did that.

I've uploaded a complete working example with additional functions for testing and generating trees for testing.

Answer 2

EDIT: I misunderstood the original question, so phoku's answer is much more relevant.

---

The logical or operator in C (and most other languages) does what's called short-circuiting: it stops evaluating operands as soon as it finds one that's true. So if hasPathSum(tree->left, sum) returns 1, hasPathSum(tree->right, sum) will never get called.

This question has a more detailed explanation. It's written for Java, but the operators in C work the same way.