CODEWITHSUNDEEP
javaalgorithmtree
ShahrukhKhan
ShahrukhKhan

Reputation: 365

Recursion related to trees

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?

Upvotes: 0

Views: 115

Answers (3)

Bernhard Barker
Bernhard Barker

Reputation: 55649

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

Upvotes: 0

Gene
Gene

Reputation: 47020

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);
    }
}

Upvotes: 1

Hegi
Hegi

Reputation: 184

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.

Upvotes: 1

Related Questions