Hi
I am trying to implement hasPathSum()
means for given number is there any path exist between root-to-leaf node.
I got this code from Stanford website. And i am thinking this is wrong
/**
Given a tree and a sum, returns true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum.
Strategy: subtract the node value from the sum when recurring down,
and check to see if the sum is 0 when you run out of tree.
*/
boolean hasPathSum(Node node, int sum) {
// return true if we run out of tree and sum==0
if (node == null){
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node.data;
return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
}
Is this a right implementation?
I am thinking this if should be
- if(node.left==null && node.right==null)
If i am wrong Please clear my confusion
consider this case:
5
/ \
2 1
/
3
-Thanks
Best Answer
You really should just code it and try it - you learn a lot that way. (Edit: I certainly am ...)
I believe the original code fails for
hasPathSum(tree, 7)
because node 2 is not a leaf.Edit:
Original code withdrawn due to obvious mistakes - obvious at least to everyone but me :-)
Edit:
My new solution is below. Note that the included optimization (
if (sum <= node.data)
) assumes the tree is made up of all positive data values. It should be removed or tweaked if the tree has zero or negative data values. (thanks @Mark Peters).Also note the discussion in the answer comments about handling
hasPathSum(null, 0)
.Full code:
Sample run: (Note case 7)