Preetam Purbia - 1 year ago 100
Java Question

# Binary Tree hasPathSum() Implementation

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

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)`.

``````static boolean hasPathSumBert(final Node node, final int sum) {
// return true if we run out of tree and sum==0
if (node == null) {                                   // empty tree
// choose one:
return (sum == 0);
//return false;
} else if (node.left == null && node.right == null) { // leaf
return (sum == node.data);
} else if (sum <= node.data) {                        // sum used up
return false;
} else {                                              // try children
return (node.left != null  && hasPathSumBert(node.left, sum - node.data)) ||
(node.right != null && hasPathSumBert(node.right, sum - node.data));
}
}
``````

Full code:

``````public class TreeTest {
static class Node {
int data;
Node left;
Node right;

Node(final int data, final Node left, final Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}

public static void main(final String[] args) {
final Node three = new Node(3, null, null);

final Node two = new Node(2, three, null);
final Node one = new Node(1, null, null);

final Node five = new Node(5, two, one);
final Node tree = five;

for (int i = 0; i <= 10; i++) {
System.out.println(i + "");
System.out.println("original = " + hasPathSum(tree, i));
System.out.println("bert     = " + hasPathSumBert(tree, i));
System.out.println("mark     = " + hasPathSumMark(tree, i));
System.out.println();
}

System.out.println("hasPathSumBert(null, 0): "+ hasPathSumBert(null, 0));
System.out.println("hasPathSumBert(null, 1): "+ hasPathSumBert(null, 1));
}

static boolean hasPathSum(final Node node, final int sum) {
// return true if we run out of tree and sum==0
if (node == null) {
return (sum == 0);
} else {
// otherwise check both subtrees
final int subSum = sum - node.data;
return (hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
}
}

static boolean hasPathSumBert(final Node node, final int sum) {
// return true if we run out of tree and sum==0
if (node == null) {                                   // empty tree
// choose one:
return (sum == 0);
//return false;
} else if (node.left == null && node.right == null) { // leaf
return (sum == node.data);
} else if (sum <= node.data) {                        // sum used up
return false;
} else {                                              // try children
return (node.left != null  && hasPathSumBert(node.left, sum - node.data)) ||
(node.right != null && hasPathSumBert(node.right, sum - node.data));
}
}

static boolean hasPathSumMark(final Node node, final int sum) {
final int subSum = sum - node.data;
if (node.left == null && node.right == null) {
return (subSum == 0);
} else {
// otherwise check both subtrees
if (node.left != null  && hasPathSumMark(node.left, subSum))
return true;
if (node.right != null && hasPathSumMark(node.right, subSum))
return true;
return false;
}
}
}
``````

Sample run: (Note case 7)

``````0
original = false
bert     = false
mark     = false

1
original = false
bert     = false
mark     = false

2
original = false
bert     = false
mark     = false

3
original = false
bert     = false
mark     = false

4
original = false
bert     = false
mark     = false

5
original = false
bert     = false
mark     = false

6
original = true
bert     = true
mark     = true

7
original = true
bert     = false
mark     = false

8
original = false
bert     = false
mark     = false

9
original = false
bert     = false
mark     = false

10
original = true
bert     = true
mark     = true

hasPathSumBert(null, 0): true
hasPathSumBert(null, 1): false
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download