medium Count Paths for a Sum

Problem Statement

Given a binary tree and a number ‘S’, find all paths in the tree such that the sum of all the node values of each path equals ‘S’. Please note that the paths can start or end at any node but all paths must follow direction from parent to child (top to bottom).

Constraints:

The number of nodes in the tree is in the range [0, 1000].
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

Try it yourself

✅ Solution Count Paths for a Sum

Problem Statement

Constraints:

The number of nodes in the tree is in the range [0, 1000].
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

Solution

This problem follows the Binary Tree Path Sum pattern. We can follow the same DFS approach. But there will be four differences:

We will keep track of the current path in a list which will be passed to every recursive call.
Whenever we traverse a node we will do two things:
Add the current node to the current path.
As we added a new node to the current path, we should find the sums of all sub-paths ending at the current node. If the sum of any sub-path is equal to ‘S’ we will increment our path count.
We will traverse all paths and will not stop processing after finding the first path.
Remove the current node from the current path before returning from the function. This is needed to Backtrack while we are going up the recursive call stack to process other paths.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

java

import java.util.*;

// class TreeNode {
//   int val;
//   TreeNode left;
//   TreeNode right;

//   TreeNode(int x) {
//     val = x;
//   }
// };

class Solution {

  public int countPaths(TreeNode root, int S) {
    List<Integer> currentPath = new LinkedList<>();
    return countPathsRecursive(root, S, currentPath);
  }

  private static int countPathsRecursive(
    TreeNode currentNode,
    int S,
    List<Integer> currentPath
  ) {
    if (currentNode == null) return 0;

    // add the current node to the path
    currentPath.add(currentNode.val);
    int pathCount = 0;
    double pathSum = 0; // let's use a double to handle integer overflow for large sums
    // find the sums of all sub-paths in the current path list
    ListIterator<Integer> pathIterator = currentPath.listIterator(
      currentPath.size()
    );
    while (pathIterator.hasPrevious()) {
      pathSum += pathIterator.previous();
      // if the sum of any sub-path is equal to 'S' we increment our path count.
      if (pathSum == S) {
        pathCount++;
      }
    }

    // traverse the left sub-tree
    pathCount += countPathsRecursive(currentNode.left, S, currentPath);
    // traverse the right sub-tree
    pathCount += countPathsRecursive(currentNode.right, S, currentPath);

    // remove the current node from the path to backtrack,
    // we need to remove the current node while we are going up the recursive call stack.
    currentPath.remove(currentPath.size() - 1);

    return pathCount;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(4);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    System.out.println("Tree has path: " + sol.countPaths(root, 11));
  }
}

Time Complexity

The time complexity of the above algorithm is in the worst case, where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once, but for every node, we iterate the current path. The current path, in the worst case, can be O(N) (in the case of a skewed tree). But, if the tree is balanced, then the current path will be equal to the height of the tree, i.e., O(logN). So the best case of our algorithm will be O(NlogN).

Space Complexity

The space complexity of the above algorithm will be O(N). This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child). We also need O(N) space for storing the currentPath in the worst case.

Overall space complexity of our algorithm is O(N).

A more efficient solution

Can we further improve the solution?

One thing we are repeating for each node is traversing the current path and seeing if any sub-path that ends at the current node gives us the required sum.

Let’s see if we can improve this part.

We can use the Prefix Sum technique to efficiently manage the path sums.

Prefix Sum

Let’s first understand what Prefix Sum is. For a given array, its Prefix Sum is another array where each element is the commutative sum of the corresponding element in the given array and all its previous elements.

Here is an example:

Now, let’s say we want to find all subarrays of a given array with a target sum.

Let’s say our target sum is 7, and we want to find all the subarrays of the array mentioned above.

We can clearly see that there are two such subarrays: 1) [1, 6], and 2) [2, 5].

How can we utilize the Prefix Sum array to find these two subarrays efficiently?

There are two ways Prefix Sum can help us:

a) Since each element of the prefix sum array contains the cumulative sum of current and previous elements, therefore, whenever we see our target sum, we have found our targeted subarray. For example, since the second element of the prefix sum array is 7; therefore, our target subarray will be from the start of the array till the second element, i.e., [1, 6]

(b) Secondly, the prefix sum array can also help us find our target subarray that is not starting from the first index.

If we subtract the target sum from any element of the prefix sum array, the result will also give us our target subarray (if that result is present in the prefix sum array).

For example, take the 4th element of the prefix sum array and subtract the target sum from it: 14 – 7 => 7

Is this result (7) present in the prefix sum array? Yes, it is the second element. This means the sum from the 3rd element to the current element (i.e., the 4th) is also 7.

Hence, our target subarray will be from the 3rd element to the current element, i.e., [2, 5].

Now, let’s see how we can use prefix sum for binary trees. Take the following example:

We can consider each path as an array and calculate its prefix sums to find any required sub-paths. In the above tree, the highlighted sub-paths are exactly the same as our previous array example.

Here is what our new algorithm will look like:

Code

Here is the code for this algorithm:

java

import java.util.*;

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int val) {
    this.val = val;
  }
}

class Solution {
  public static int countPaths(TreeNode root, int targetSum) {
    // A map that stores the number of times a prefix sum has occurred so far.
    Map<Integer, Integer> map = new HashMap<>();

    return countPathsPrefixSum(root, targetSum, map, 0);
  }

  public static int countPathsPrefixSum(TreeNode node, int targetSum, Map<Integer, Integer> map,
      Integer currentPathSum) {
    if (node == null)
      return 0;

    // The number of paths that have the required sum.
    int pathCount = 0;

    // 'currentPathSum' is the prefix sum, i.e., sum of all node values from the root to
    // the current node.
    currentPathSum += node.val;

    // This is the base case. If the current sum is equal to the target sum, we have
    // found a path from root to the current node having the required sum. Hence, we 
    // increment the path count by 1.
    if (targetSum == currentPathSum)
      pathCount++;

    // 'currentPathSum' is the path sum from root to the current node. If within
    // this path, there is a valid solution, then there must be an 'oldPathSum' such that:
    // => currentPathSum - oldPathSum = targetSum
    // => currentPathSum - targetSum = oldPathSum
    // Hence, we can search such an 'oldPathSum' in the map from the key
    // 'currentPathSum - targetSum'.
    pathCount += map.getOrDefault(currentPathSum - targetSum, 0);

    // This is the key step in the algorithm. We are storing the number of times the
    // prefix sum `currentPathSum` has occurred so far.
    map.put(currentPathSum, map.getOrDefault(currentPathSum, 0) + 1);

    // Counting the number of paths from the left and right subtrees.
    pathCount += countPathsPrefixSum(node.left, targetSum, map, currentPathSum);
    pathCount += countPathsPrefixSum(node.right, targetSum, map, currentPathSum);

    // Removing the current path sum from the map for backtracking.
    // 'currentPathSum' is the prefix sum up to the current node. When we go back
    // (i.e., backtrack), then the current node is no more a part of the path, hence, w
    // e should remove its prefix sum from the map.
    map.put(currentPathSum, map.getOrDefault(currentPathSum, 1) - 1);

    return pathCount;
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(4);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    System.out.println("Tree has path: " + Solution.countPaths(root, 11));
  }
}

Time Complexity

As we are not traversing the current path for each node, the time complexity of the above algorithm will be O(N) in the worst case, where ‘N’ is the total number of nodes in the tree.

Space Complexity

The space complexity of the above algorithm will be O(N). This space will be used to store the recursion stack, as well as for the prefix sum.

🤖 Don't fully get this? Learn it with Claude

Stuck on Count Paths for a Sum? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Count Paths for a Sum** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Count Paths for a Sum** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Count Paths for a Sum**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Count Paths for a Sum**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Path With Given Sequence Check if all leaves are at same le →