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 (n开发者_运维百科ode == 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

Since Bert isn't fixing his answer, I'll post the correct one.

Yes, you're right that the original code is broken, despite what most people here are saying. In your example

      5
     / \
    2   1
   /    
  3

Calling

hasPathSum(root, 7);

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

The fix is inspired by Bert'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 roll the else block into one long statement if you want (lots of ands and ors), but I find this cleaner.

Hi guys Thanks for your answers, this discussion seems very intersting, last night again i tried to implement this function and i think my solution will work for all cases,

actually I implemented in simpler way so that it can be understandable by everyone

There are four cases to check

1. if both childs are null (our targeted case)
2. if only right child exists (means left child is null)
3. if only left child exists (means right child is null)
4. if both childs exists (means node is having left and right childs)

One special case: if you pass input tree directly as null then it is required to handle (one more if block req.)

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

Please review my code will this work for all the binary tree cases? and let me know if any changes are required.

-Thanks

OP's function clearly fails for the following simple case:

   1
    \
     2

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

This happens because the changing sub-sum should be compared to zero only when we reach a leaf node(empty left sub-tree and empty right sub-tree) or a special case of an empty tree.

OP's function is treating any node with NULL child as leaf.

The following function( which is same as Mark's + 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: Ideone Link

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

Additionally, the nums list would store all root-to-leaf paths sums. I added this just to make sure that my code wasn't generating 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;

}

try this

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