Tree - path sum

Question

Question -> Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

My Solution ->

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null || sum == 0){
            return false;
        }
        List<Integer> resultSet = new ArrayList<Integer>();
        Integer result = root.val;
        inorder(root, result, resultSet);
        return resultSet.contains(sum);
    }
    public void inorder(TreeNode root, Integer result, List<Integer> resultSet){
        if (root.left == null && root.right == null){
            resultSet.add(result);
        }
        if (root.left != null) {
            result += Integer.valueOf(root.left.val);
            inorder(root.left, result, resultSet);
        }
        if (root.right != null) {
            result += Integer.valueOf(root.right.val);
            inorder(root.right, result, resultSet);
        }

    }
}

Output ->

Input: [1,-2,-3,1,3,-2,null,-1] 3 Output: true Expected: false

I am really not sure where I am going wrong with this. I tried playing with the int and Integer type options for result , but it didn't work. Please help.

pgiitu pgiitu · Accepted Answer · 2015-10-17T23:45:00

The problem I see is with result variable as once you add the value of left node to the result and are done with the left subtree then u will add the value of right child to the result, which is wrong as now it is has the sum of both left and right child value.

So essentially you are adding the values of all the nodes in the result that come before the node root in the inorder traversal.

Can you try this:

public void inorder(TreeNode root, Integer result, List<Integer> resultSet){
    if (root.left == null && root.right == null){
        resultSet.add(result);
    }
    if (root.left != null) {
        inorder(root.left, result+Integer.valueOf(root.left.val), resultSet);
    }
    if (root.right != null) {
        inorder(root.right, result+Integer.valueOf(root.right.val), resultSet);
    }
}

EDIT:1

Another simple approach to solve this problem: You don't need to create a array which contains the sum of all the root to leaf paths. You can simply keep decrementing the required sum.

Code:

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    } else {
        return hasPathSumHelper(root, sum);
    }

}

boolean hasPathSumHelper(TreeNode root, int sum) {
    if (root.left == null && root.right == null) {//if leaf node
        if (Integer.valueOf(root.val) == sum) { //if node value is equal to sum
            return true;
        } else {
            return false;
        }
    }
    if ((root.left != null) && (root.right != null)) {
        return (hasPathSumHelper(root.left, sum - Integer.valueOf(root.val)) || hasPathSumHelper(root.right, sum - Integer.valueOf(root.val)));
    }
    if (root.left != null) {
        return hasPathSumHelper(root.left, sum - Integer.valueOf(root.val));
    } else {
        return hasPathSumHelper(root.right, sum - Integer.valueOf(root.val));
    }
}

Tree - path sum

1 Answers