# O(n^2), prefix sum - O(n)

• Lets consider any path starting from root till leaf as a sequence. Now we have an array of integer values. We need to calculate number of sums (a[i] + a[i+1] + ... + a[j], i<j) which will be equal to a target. We can do it by fixing two positions for N^2.

``````public class Solution {

public int pathSum(TreeNode root, int sum) {
if (root==null) {
return 0;
}

int childSum = pathSum(root.left, sum) + pathSum(root.right, sum);
return suffixPathSum(root, 0, sum) + childSum;
}

private int suffixPathSum(TreeNode node, int curSum, int target) {
if (node==null) {
return 0;
}

int cnt = 0;
if (curSum+node.val==target) {
cnt++;
}

cnt += suffixPathSum(node.left, curSum+node.val, target);
cnt += suffixPathSum(node.right, curSum+node.val, target);

return cnt;
}
}
``````

O(n) solution. Lets calculate prefix sum for each position.
We know that prefixSum - target = X. Now its enough to know how many times prefix sum with value X was meet till this position. For storing that we can use map.

``````
public class Solution {

public int pathSum(TreeNode root, int sum) {
HashMap<Integer, Integer> prefSumCounter = new HashMap<>();
prefSumCounter.put(0,1);
return calculatePrefSum(root, 0, sum, prefSumCounter);
}

private int calculatePrefSum(TreeNode node, int prefSum, int target, HashMap<Integer, Integer> prefSumCounter) {
if (node==null) return 0;
int nSum = prefSum+node.val;

int x = nSum-target;
int counter = prefSumCounter.getOrDefault(x,0);

prefSumCounter.putIfAbsent(nSum, 0);
prefSumCounter.put(nSum, prefSumCounter.get(nSum)+1);

counter += calculatePrefSum(node.left, nSum, target, prefSumCounter);
counter += calculatePrefSum(node.right, nSum, target, prefSumCounter);

prefSumCounter.put(nSum, prefSumCounter.get(nSum)-1);
if (prefSumCounter.get(nSum)<=0) prefSumCounter.remove(nSum);

return counter;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.