HasPathSum () Binary Tree Implementation

Question

Hi I am trying to implement hasPathSum() for a given number, is there any way between the root-to-leaf node.

I got this code from the Stanford website. And I think 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 the correct implementation?

I think that if it should be

• if (node.left == null && node.right == null)

If I'm wrong, please clear my confusion

consider this case:

  5 / \ 2 1 / 3 

-Thanks

Answer 1

You really just need to code it and try it - you will learn so much. (Editing: I certainly ...)

I believe the source code does not work for hasPathSum(tree, 7) , because node 2 is not a leaf.

Edit:

The original code was shot due to obvious errors - obviously, at least for everyone except me :-)

Edit:

My new solution is below. Please note that the included optimization ( if (sum <= node.data) ) assumes that the tree is composed of all positive values. It must be deleted or changed if the tree has zero or negative data values. (thanks @Mark Peters).

Also take a look at the discussion of comments on the hasPathSum(null, 0) processing 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; } } } 

Run example: (Case with record 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 

Answer 2

Since Bert does not record his answer, I will send the correct one.

Yes, you are correct that the source code is broken, despite what most people say. In your example

  5 / \ 2 1 / 3 

Call

 hasPathSum(root, 7); 

will return true , despite the fact that there is no path from root-to-leaf, which adds 7. This is because when node 2 reached, it recursively checks the correct child (with the sum 0), which then returns true because the right child null

The fix is ​​inspired by Burt's answer:

 // `if` statement should check children and `return` statement deduct node.data from sum boolean hasPathSum(Node node, int sum) { int subSum = sum - node.data; if(node.left==null && node.right==null) { return(subSum == 0); } else { // otherwise check both subtrees if ( node.left != null && hasPathSum(node.left, subSum) ) { return true; if ( node.right != null && hasPathSum(node.right, subSum) ) { return true; } return false; } } 

You can collapse the else block into one long statement if you want (lots of ands and ors), but I find this cleaner.

Answer 3

Hi guys Thanks for your answers, this discussion seems very interesting, last night I tried to implement this feature, and I think that my solution will work for all cases,

I’m actually implemented in a simpler way so that it can be understood by everyone

---

There are four cases to check.

• if both children are null (our target case)
• if only the correct child exists (means that the left child is null)
• if only the left child exists (means the right child is null)
• if both children exist (means that node has left and right children)

One special case : if you pass the input tree directly as null, then you need to process it (another block option)

  public static boolean hasPathSum(TNode root, int sum) { if(root==null) //it is called only if you pass directly null return false; int subsum = sum-root.data; //if(subsum<0) return false; //uncomment this for reducing calls for negative numbers if(root.left==null && root.right==null) //for leaf node return (subsum==0); if(root.left==null) //if only right child exist return hasPathSum(root.right, subsum); if(root.right==null)//if only left child exist return hasPathSum(root.left, subsum); return (hasPathSum(root.left, subsum) || hasPathSum(root.right,subsum)); } 

Read my code, will this work for all binary tree cases? and also let me know if any changes are required.

-Thanks

Answer 4

The OP function obviously fails in the following simple case:

  1 \ 2 

The above tree as one root to the path sheet of the sum 3 . But the OP function will return true for hasPathSum(root,1)

This is because the changing subasum should be compared with zero only when we reach the leaf node (empty left subtree and empty right subtree) or a special case of an empty tree.

The OP function treats any node with a NULL child as a leaf.

The following function (same as Mark + one additional check) fixes it:

 boolean hasPathSum(Node node, int sum) { // CASE 1: empty tree. if (node == NULL) { return sum == 0; } // CASE 2: Tree exits. int subSum = sum - node.data; // CASE 2A: Function is called on a leaf node. if (node.left==null && node.right==null) { return subSum == 0; // CASE 2B: Function is called on a non-leaf node. } else { // CASE 2BA: Non-left node has desired path in left subtree. if (node.left != null && hasPathSum(node.left, subSum) ){ return true; } // CASE 2BB: Non-left node has desired path in right subtree. if ( node.right != null && hasPathSum(node.right, subSum) ) { return true; } // CASE 2BC: Non-left node has no desired pat. return false; } } 

C version: Perfect link

Answer 5

Here is an alternative approach that calculates the sum of each path and compares it with the target value. IMHO, this seems more intuitive than using the logic of subscriptions.

In addition, the nums list will store all the amounts of empty lines. I added this just to make sure my code does not create any unwanted paths.

 public static boolean hasPathSum(Node root, int sum, int val, ArrayList<Integer> nums) { if(root == null) { return (sum == 0); } val = val + root.data; if(root.right == null && root.left == null) { nums.add(val); return (val == sum); } boolean left = hasPathSum(root.left, sum, val, nums); boolean right = hasPathSum(root.right, sum, val, nums); return left || right; } 

Answer 6

try it

  bool hasPathSum(struct node* node, int sum){ if(node == NULL){ return false; } if((sum - (node->data) == 0) && (node->left == NULL) && (node->right == NULL) ) { return true; } if (sum - (node->data) < 0) { return false; } else { return( hasPathSum (node->left,sum - ( node->data ) ) || hasPathSum (node->right, sum - (node->data) ) ); } }