medium Path Sum III

Problem Statement

Given the root of a binary tree and an integer targetSum, return the count of number of paths in the tree where the sum of the values along the path equals targetSum.

A path can start and end at any node, but it must go downward, meaning it can only travel from parent nodes to child nodes.`

Examples

Example 1:

• Input: targetSum = 10, root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

      1
     / \
    2   3
   / \ / \
  4  5 6  7
 / \ /
8  9 10

• Expected Output: 3
• Justification: The paths that sum to 10 are:
  • 1 → 3 → 6
  • 3 → 7
  • 10

Example 2:

• Input: targetSum = 12, root = [5, 4, 6, 3, null, 7, 8, null, null, 2, 1]

    5
   / \
  4   6
 /   / \
3   7   8
   / \      
   2  1

• Expected Output: 1
• Justification: The paths that sum to 12 are:
  • 5 → 4 → 3

Example 3:

• Input: targetSum = 18, root = [10, 5, -3, 3, 2, null, 11, null, null, 1]

   10
   / \
  5  -3
 / \   \
3   2   11
   / 
  1 

• Expected Output: 3
• Justification: The path that sums to 18 is:
  • 10 → 5 → 3
  • 10 → -3 → 11
  • 10 → 5 → 2 → 1

Constraints:

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

Solution

To solve this problem, we need to explore all possible paths in the tree and check if any of them sum up to targetSum. We can use a depth-first search (DFS) approach to traverse the tree. During the traversal, we'll maintain a current path and calculate the running sum of the nodes in this path. To efficiently find the number of paths that sum to the target, we can use a hash map to store the cumulative sums we encounter and their frequencies. This way, for any node, we can determine if there is a sub-path (ending at the current node) whose sum equals targetSum by checking if (currentSum - targetSum) exists in the hash map.

This approach ensures we efficiently count all valid paths without having to repeatedly traverse the same nodes, making it more effective than a brute-force solution. The use of a hash map helps us keep track of the cumulative sums and their frequencies, allowing quick lookups and updates.

Step-by-step Algorithm

1. Initialization:

   • Create a hash map prefixSumCount to store the cumulative sums and their frequencies. Initialize it with {0: 1} to handle the base case where a path itself equals targetSum.

2. Define DFS Function and Add Base Case:

   • Create a helper function dfs(node, currSum, targetSum, prefixSumCount).
   • If the current node is null, return 0 as there are no paths through this node.

3. Update Current Sum:

   • Add the value of the current node to currSum.

4. Calculate Paths:

   • Check if (currSum - targetSum) exists in prefixSumCount. This gives the number of valid paths that end at the current node.
   • Retrieve the count from the hash map and store it in numPathsToCurr.

5. Update Prefix Sum:

   • Update prefixSumCount with the current sum. Increment its count by 1.

6. DFS Recursion:

   • Recursively call dfs on the left child.
   • Recursively call dfs on the right child.
   • Sum the results of the recursive calls with numPathsToCurr.

7. Go Back to the Parent Node:

   • After processing both children, decrement the count of currSum in prefixSumCount by 1 to go back to the parent node.

8. Return Result:

   • Return the total number of paths found.

Algorithm Walkthrough

Input:

• root = [10, 5, -3, 3, 2, null, 11, null, null, 1]
• targetSum = 18

1. Initialization:

   • prefixSumCount = {0: 1}
   • Start DFS with the root node (10).

2. At Node 10:

   • currSum = 0 + 10 = 10
   • numPathsToCurr = prefixSumCount.get(10 - 18, 0) = 0
   • prefixSumCount = {0: 1, 10: 1}
   • Recur to left child (5).

3. At Node 5:

   • currSum = 10 + 5 = 15
   • numPathsToCurr = prefixSumCount.get(15 - 18, 0) = 0
   • prefixSumCount = {0: 1, 10: 1, 15: 1}
   • Recur to left child (3).

4. At Node 3:

   • currSum = 15 + 3 = 18
   • numPathsToCurr = prefixSumCount.get(18 - 18, 0) = 1
   • prefixSumCount = {0: 1, 10: 1, 15: 1, 18: 1}
   • Total paths that end at node 3: 1.

5. At Node 5 (continued):

   • Recur to right child (2).

6. At Node 2:

   • currSum = 15 + 2 = 17
   • numPathsToCurr = prefixSumCount.get(17 - 18, 0) = 0
   • prefixSumCount = {0: 1, 10: 1, 15: 1, 17: 1}
   • Recur to left child (null).
     • Return 0.

7. At Node 2 (continued):

   • Recur to right child (1).

8. At Node 1:

   • currSum = 17 + 1 = 18
   • numPathsToCurr = prefixSumCount.get(18 - 18, 0) = 1
   • prefixSumCount = {0: 1, 10: 1, 15: 1, 17: 1, 18: 1}
   • Total paths that end at node 1: 1.

9. At Node 2 (continued):

   • prefixSumCount = {0: 1, 10: 1, 15: 1, 17: 0}
   • Backtrack to node 5.
   • Total paths from node 2: 1.

10. At Node 5 (continued):

    • prefixSumCount = {0: 1, 10: 1, 15: 0}
    • Backtrack to node 10.
    • Total paths from node 5: 2.

11. At Node 10 (continued):

    • Recur to right child (-3).

12. At Node -3:

    • currSum = 10 - 3 = 7
    • numPathsToCurr = prefixSumCount.get(7 - 18, 0) = 0
    • prefixSumCount = {0: 1, 10: 1, 7: 1}
    • Recur to left child (null).
      • Return 0.

13. At Node -3 (continued):

    • Recur to the right child (11).

14. At Node 11:

    • currSum = 7 + 11 = 18
    • numPathsToCurr = prefixSumCount.get(18 - 18, 0) = 1
    • prefixSumCount = {0: 1, 10: 1, 7: 1, 18: 1}
    • Recur to left child (null).
      • Return 0.

15. At Node 11 (continued):

    • Recur to right child (null).
      • Return 0.
    • prefixSumCount = {0: 1, 10: 1, 7: 1, 18: 0}
    • Backtrack to node -3.
    • Total paths that end at node 11: 1.

16. At Node -3 (continued):

    • prefixSumCount = {0: 1, 10: 1, 7: 0}
    • Backtrack to node 10.
    • Total paths from node -3: 1.

17. At Node 10 (continued):

    • prefixSumCount = {0: 1, 10: 0}
    • Total paths from node 10: 3.

Total Paths: 3 (10→5→3, 10→5→2→1, 10→-3→11)

Code

import java.util.HashMap;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {

  public int pathSum(TreeNode root, int targetSum) {
    // Initialize a hashmap to store the prefix sums and their frequencies
    HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
    prefixSumCount.put(0, 1); // Base case: one way to get sum = 0

    // Call the DFS helper function
    return dfs(root, 0, targetSum, prefixSumCount);
  }

  private int dfs(
    TreeNode node,
    int currSum,
    int targetSum,
    HashMap<Integer, Integer> prefixSumCount
  ) {
    if (node == null) return 0;

    currSum += node.val; // Update the current sum
    // Calculate the number of valid paths ending at the current node
    int numPathsToCurr = prefixSumCount.getOrDefault(currSum - targetSum, 0);

    // Update the prefix sum count for the current sum
    prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);

    // Recursively call DFS on the left and right children
    int result =
      numPathsToCurr +
      dfs(node.left, currSum, targetSum, prefixSumCount) +
      dfs(node.right, currSum, targetSum, prefixSumCount);

    // Remove the current sum from the prefix sum count (backtrack)
    prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);

    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test Case 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.left = new TreeNode(4);
    root1.left.right = new TreeNode(5);
    root1.right.left = new TreeNode(6);
    root1.right.right = new TreeNode(7);
    root1.left.left.left = new TreeNode(8);
    root1.left.left.right = new TreeNode(9);
    root1.left.right.left = new TreeNode(10);
    System.out.println(solution.pathSum(root1, 10)); // Expected Output: 3

    // Test Case 2
    TreeNode root2 = new TreeNode(5);
    root2.left = new TreeNode(4);
    root2.right = new TreeNode(6);
    root2.left.left = new TreeNode(3);
    root2.right.left = new TreeNode(7);
    root2.right.right = new TreeNode(8);
    root2.right.left.left = new TreeNode(2);
    root2.right.left.right = new TreeNode(1);
    System.out.println(solution.pathSum(root2, 12)); // Expected Output: 1

    // Test Case 3
    TreeNode root3 = new TreeNode(10);
    root3.left = new TreeNode(5);
    root3.right = new TreeNode(-3);
    root3.left.left = new TreeNode(3);
    root3.left.right = new TreeNode(2);
    root3.right.right = new TreeNode(11);
    root3.left.right.right = new TreeNode(1);
    System.out.println(solution.pathSum(root3, 18)); // Expected Output: 3
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (N) is the number of nodes in the binary tree. This is because each node is visited exactly once in the depth-first search traversal.

Space Complexity

The space complexity is also due to the space required for the hash map (prefixSumCount) and the recursion stack in the worst case when the binary tree is completely unbalanced.