algoadvance

Leetcode 437. Path Sum III

Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Clarifying Questions

1. Can the tree contain negative numbers?
   • Yes, the tree values can be negative.
2. What is the expected range of input size?
   • Generally, trees with about 10^4 nodes can be expected.
3. Can the target sum be negative?
   • Yes, the target sum can be negative.
4. Is the path necessarily continuous?
   • Yes, the path is continuous going downwards from parent nodes to child nodes.

Strategy

The problem can be seen as finding all paths in the tree such that the sum of nodes in the path equals targetSum. We’ll use two main strategies to solve this problem:

1. Depth First Search (DFS):
   • Traverse each node and consider it as the starting point for a potential path.
   • Use a helper function to explore all downward paths from any starting node.
2. Prefix Sum:
   • Use a prefix sum to efficiently count the number of valid paths during the DFS traversal.

The key idea with the prefix sum approach is:

• Maintain a running sum while traversing the tree.
• Use a hashmap to store the frequency of all prefix sums encountered so far.
• For each node, calculate the current sum and the difference with the target sum to determine if a valid path ends at the current node.

Code

#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> prefixSumMap;
        prefixSumMap[0] = 1;  // Base case: a path sum equal to the targetSum itself.
        return dfs(root, 0, targetSum, prefixSumMap);
    }
    
private:
    int dfs(TreeNode* node, long currentSum, int targetSum, unordered_map<long, int>& prefixSumMap) {
        if (!node) return 0;
        
        currentSum += node->val;
        int numPathsToCurr = prefixSumMap[currentSum - targetSum];
        
        prefixSumMap[currentSum]++;
        
        int numPathsInLeftSubtree = dfs(node->left, currentSum, targetSum, prefixSumMap);
        int numPathsInRightSubtree = dfs(node->right, currentSum, targetSum, prefixSumMap);
        
        prefixSumMap[currentSum]--;
        
        return numPathsToCurr + numPathsInLeftSubtree + numPathsInRightSubtree;
    }
};

Time Complexity

• Time Complexity: The time complexity is (O(N)), where (N) is the number of nodes in the tree. This is because each node is visited once, and prefix sum operations are (O(1)).

• Space Complexity: The space complexity is (O(H)) for the recursion stack, where (H) is the height of the tree, plus the space required for the prefix sum hashmap. In the worst case, the height of the tree could be (N), resulting in (O(N)) space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?