CODEWITHSUNDEEP
java
sssszzzzzzssszzz
sssszzzzzzssszzz

Reputation: 163

Why doesn't this algorithm work for path sum in a tree?

You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

I wrote this up:

EDIT: Fixed algo, but fails on a test case.

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    public int helper(TreeNode node, int sum){
        if(node == null) return 0;
        if(node.val == sum) return 1;
        return helper(node.left, sum - node.val) + helper(node.right, sum - node.val);
    }

}

Upvotes: 1

Views: 133

Answers (1)

user4668606
user4668606

Reputation:

In the return-statement these two recursive calls are included:

pathSum(root.right, sum) + pathSum(root.left, sum)

Complete:

return pathSum(root.left, sum - root.val) + pathSum(root.right, sum - root.val) + pathSum(root.right, sum) + pathSum(root.left, sum);

This basically means that you allow the traversal to skip nodes in the middle of the path. E.g. the path 10 -> 5 -> 3 -> -2 would be part of the solution as well, since 10 + (-2) = 8.

Now for the fix:
You need to keep track of all sums that can be found on a certain path through the tree. A way of solving this would be to keep an accumulative list of numbers:

public int pathSum(TreeNode n, Stack<Integer> acc, int sum){
    if(n == null){
        return 0;
    }

    int count = 0;
    int totalToNode = acc.peek() + n.val;

    //increment count, if the nodes value matches (path of length 1)
    if(n.val == sum)
        count++;

    //increment count, if the path from root to n sums up to the given value
    if(totalToNode == num)
        count++;

    //find all paths that end in n and sum up to the searched sum
    for(int s : acc)
        if(totalToNode - s == sum)
            count++;

    acc.push(totalToNode);

    //number of matching paths for left and right subtree
    count += pathSum(n.left, acc, sum);
    count += pathSum(n.right, acc, sum);

    acc.pop();

    return count;
}

This solution represents a path as a list of values of nodes and finds all subsequences ending at the current node which sum up to a given value. This way no path will be covered twice.

Upvotes: 1

Related Questions