0

Here's code which finds a root-to-leaf path that equals to a particular sum:

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }  
    if (root.left==null && root.right==null) {
        return (sum == root.val);
    }   
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

Even when one recursive call returns true (with return (sum==root.val)), I don't understand how the original function call is true.

My understanding is that in the stack, that particular activation record is true, but then wouldn't the other calls on the stack return false; clearly the remaining might not be a path, and wouldn't that render it all as false? How does it attach importance to that if statement?

Improve this question

3 Answers 3

Reset to default
1

This is actually not coded in the clearest manner.

Recursion is always about solving a problem by using the same procedure (function) to solve one or more smaller versions of the same problem, then combining these solutions.

In this case, the smaller problems are to check for the rest of the required sum in the left and right subtrees (if they exist).

We can stop after the left if successful, skipping the right. In this manner, the "leftmost" path in the tree with the desired sum is found. We have no need to find any others.

When checking a subtree, we subtract the value of the current node from the desired sum. Intuitively this is making the problem "smaller" as described above.

I'll add comments that show the logic.

public boolean hasPathSum(TreeNode root, int sum) {
    // If we've reached a null child, the other child is non-null,  so we're
    // not at a leaf, so there no way this can be a leaf-to-path sum.
    // See below for why this is the case.
    if (root == null) {
        return false;
    }
    // If we're at a leaf (null children), then we've found the path
    // if and only if the node value exactly equals the sum we're looking for. 
    if (root.left == null && root.right == null) {
        return (sum == root.val);
    }
    // We're not at a leaf.  See if we can find the remaining part of the sum
    // by searching the children.  Null children are handled above.  If the
    // sum is found in the left subtree, the short-circuit evaluation of ||
    // will skip searching the right.
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

Note that it possibly doesn't make sense that

hasPathSum(null, 0)

returns false in this code. I'd do it this way:

class TreeNode {
    // ... skipping other TreeNode fields.
    public boolean isLeaf() { return left == null && right == null; } 
    public boolean hasPathSum(int sum) {
        return isLeaf() ? sum == val : 
            (left != null && left.hasPathSum(sum - val)) ||
            (right != null && right.hasPathSum(sum - val);
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

but even when it finds it, and returns, doesn't have to complete the remaining activations calls on the stack? And isn't the 'last' return value what renders a statement true or false? Please give me a hand here. :-)
Sure. And it does complete all those activations. All of them must be executing in one or the other branch of the || operation because this is where the recursive calls are. As soon as a true is returned at a leaf, each of the ||s on the stack will also evaluate to true, which causes true to immediately be returned, unwinding the stack. (A clever implementation might throw an exception when the sum is found to unwind the stack all the way in one big step.) However you should not worry too much about these mechanisms. The principle of decomposing into subproblems is the key.
"The principle of decomposing into subproblems is the key" wise words; I keep on worrying about the inner details, and try to draw out the activation records; How do you suggest I improve my ability in decomposing the original problem into sub-problems? I mean, I certainly envied how quickly you were able to code your version up. Please offer some suggestions.
Practice! Find lots of little problems like this. Try them. Look at others' solutions. It's a way of thinking. After you've done it a few times, the way of thinking comes more naturally. Try searching for "recursive algorithm examples". There are a few reasonably good pages out there.
1

Here is a good visualisation for recursion. Basically, when you call hasPathSum it 1st checks if root is null. If it's null, then it will return with a false.

If root is not null, then it goes further. if left and right both nulls then you are at a leaf node. If the leaf node has the same value as the root, then you'll return with true. Otherwise it will be a false.

If both if statements were skipped it means, that either the left, or the right (or both) has more nodes. Then the root node will become the your left and right, and you'll check for the sum value there, and return with the result from them.

Let's assume that this is your tree and the leaf4 has the desired value:

            root
     left           right
leaf1    -       leaf3  leaf4  


----------- 1st depth, with root node ---------------
hasPathSum(root)
root==null //false, so it moves on
root.left // is 'left', so skipping
hasPathSum(left) || hasPathSum(right) // this statement will be evaluated

------------- 2nd depth, with left node ---------------
hasPathSum(left)
left==null //false, so it moves on
left.left // is 'leaf1', so skipping
hasPathSum(leaf) || hasPathSum(null) // this statement will be evaluated

------------- 3rd depth, with leaf1 node ---------------
hasPathSum(leaf1)
leaf1==null //false, so it moves on
leaf1.left and leaf1.right // are both null, so returnin with sum == root.val

------------- 3rd depth, with - node ---------------
hasPathSum(-)
-==null //true, so it returns with false

------------- 2nd depth, with left node ---------------
false || false // is false, so it will return with false

------ in this moment, hasPathSum(left) part of 1st depth's has been evaulated to false
so hasPathSum(right) has to be ecaluated as well.

It wont be any different from the code above, except that when processing leaf4, the sum==root.val will be true, so the whole thing will return true. Hope this helps.

Improve this answer

Comments

0

A simple example explained might help.

Let's consider a tree like this:

  5
 / \
2   3
     \
      1

And we're looking for a sum of 9.

Now the recursive calls will look like this:
(my indentation is such that each statement is executed by the function at the previous level of indentation)

hasPathSum(N5, 9)
   hasPathSum(N2, 9-5 = 4)
      return false // since 2 != 4
   hasPathSum(N3, 9-5 = 4)
      hasPathSum(null, 4-3 = 1) // left child of N3
          return false // since root == null
      hasPathSum(N1, 4-3 = 1)
          return true // since 1 == 1
      return (false || true) = true
   return (false || true) = true
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.