Path Sum III

Med

#0424Time: O(N^2) in the worst case (a skewed tree) and O(N log N) in the average case (a balanced tree), where N is the number of nodes. For each of the N nodes, we traverse its subtree, which takes O(H) time, where H is the height of the subtree.Space: O(N) in the worst case (a skewed tree) and O(log N) in the average case (a balanced tree). The space is determined by the maximum depth of the recursion stack.3 companies

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Companies

Flipkart Zepto NetApp

Prompt

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).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is a straightforward, brute-force solution that directly translates the problem statement into a recursive algorithm. It considers every possible starting node for a path. For each node in the tree, it initiates a separate downward traversal to find all paths starting from that node that sum up to the targetSum. The final result is the sum of counts from all possible starting nodes.

Algorithm

The overall strategy involves a double recursion.

The main recursive function, pathSum(node, targetSum), traverses every node in the tree.
For each node, it calculates the total number of valid paths by summing up three values:
- The number of valid paths that start at the current node.
- The number of valid paths found in the left subtree (by recursively calling pathSum on node.left).
- The number of valid paths found in the right subtree (by recursively calling pathSum on node.right).
A helper function, countPathsFromNode(node, currentSum, targetSum), is used to find the number of paths that start at a specific node and sum to targetSum.
This helper function traverses downwards from the given node.
- It takes the current node, the sum accumulated so far on the current path (currentSum), and the targetSum.
- If currentSum + node.val equals targetSum, a valid path is found.
- It continues to search for longer paths by recursively calling itself on the left and right children with the updated currentSum.

Walkthrough

The solution uses a pair of recursive functions. The main function, pathSum, iterates through all nodes in the tree. For each node, it treats it as a potential starting point for a valid path. It calls a helper function, countPathsFromNode, to count all valid paths that begin at this specific node and extend downwards.

The pathSum function's result for a given node is the sum of:

The number of valid paths starting at the current node (calculated by countPathsFromNode).
The number of valid paths that exist entirely within the left subtree (found by a recursive call to pathSum on the left child).
The number of valid paths that exist entirely within the right subtree (found by a recursive call to pathSum on the right child).

This method ensures that every possible downward path is considered. To prevent integer overflow with potentially large node values and path lengths, path sums are accumulated using a long data type.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int pathSum(TreeNode root, int targetSum) {18        if (root == null) {19            return 0;20        }21        // Count paths starting from the current root, plus paths in left/right subtrees.22        return countPathsFromNode(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);23    }24    25    // Helper function to count paths starting from a given node that sum to the target.26    // Note: We use a long for the current sum to avoid overflow.27    private int countPathsFromNode(TreeNode node, long targetSum) {28        if (node == null) {29            return 0;30        }31        32        int count = 0;33        // Check if the current node itself completes a path.34        if (node.val == targetSum) {35            count = 1;36        }37        38        // Continue the path downwards and see if longer paths also sum to the target.39        long remainingSum = targetSum - node.val;40        count += countPathsFromNode(node.left, remainingSum);41        count += countPathsFromNode(node.right, remainingSum);42        43        return count;44    }45}

Complexity

Time

O(N^2) in the worst case (a skewed tree) and O(N log N) in the average case (a balanced tree), where N is the number of nodes. For each of the N nodes, we traverse its subtree, which takes O(H) time, where H is the height of the subtree.

Space

O(N) in the worst case (a skewed tree) and O(log N) in the average case (a balanced tree). The space is determined by the maximum depth of the recursion stack.

Trade-offs

Pros

Relatively simple to conceptualize and implement.
The logic directly follows the problem's definition without complex data structures.

Cons

Highly inefficient due to a large number of redundant calculations. The sum for the same subpath is computed multiple times.
The time complexity is quadratic in the worst-case scenario, which can be too slow for large trees.

This optimized approach leverages the concept of prefix sums to solve the problem in a single pass. As we traverse the tree from the root downwards, we maintain the sum of the path from the root to the current node (the prefix sum). The sum of any path between an ancestor node A and a descendant node B can be calculated as prefixSum(B) - prefixSum(A). We are looking for paths where this difference equals targetSum.

By rearranging the equation to prefixSum(A) = prefixSum(B) - targetSum, we can see that for each node B, we just need to find how many of its ancestors A have a prefix sum that matches this required value. A hash map is used to efficiently store and retrieve the frequencies of prefix sums encountered on the current path from the root.

Algorithm

Initialize a global count to 0 and a HashMap<Long, Integer> named prefixSumCount to store the frequencies of prefix sums encountered.
Add an initial entry {0L: 1} to prefixSumCount. This is a crucial base case that handles paths starting from the root node.
Define a recursive DFS function, dfs(node, currentSum).
Inside dfs: a. If node is null, return. b. Update the currentSum by adding the current node.val. The currentSum represents the prefix sum from the root to the current node. c. Calculate the complement sum needed: complement = currentSum - targetSum. Check if this complement exists as a key in prefixSumCount. If it does, it means there are prefixSumCount.get(complement) paths ending at the current node that sum to targetSum. Add this number to the global count. d. Update the map for the current path: Increment the frequency of currentSum in prefixSumCount. e. Recursively call dfs for the left and right children. f. Backtrack: After the recursive calls for the children return, decrement the frequency of currentSum in prefixSumCount. This step is vital to ensure that prefix sums from one branch do not interfere with calculations in a sibling branch.

Walkthrough

This method performs a single depth-first traversal (DFS) of the tree. A hash map, prefixSumCount, is used to keep track of the cumulative sums from the root to the nodes on the current path and their frequencies.

For any node curr, the path sum from the root to curr is currentSum. If there was a previous node prev on the same path from the root with a path sum of prevSum, then the sum of the path from prev to curr is currentSum - prevSum. We want this to be equal to targetSum, so currentSum - prevSum = targetSum, which implies prevSum = currentSum - targetSum.

So, as we traverse to a node curr, we calculate its currentSum. Then, we check the hash map to see how many times we have previously seen a prefix sum of currentSum - targetSum. This count gives us the number of valid paths ending at the current node curr.

After processing a node, we add its currentSum to the map before visiting its children. After the recursive calls to its children return (i.e., after exploring its entire subtree), we must remove its currentSum from the map (backtrack). This is essential because the prefix sums of one subtree should not be available to its sibling subtree.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16import java.util.HashMap;17import java.util.Map;18 19class Solution {20    int count = 0;21    int k;22    Map<Long, Integer> prefixSumCount = new HashMap<>();23 24    public int pathSum(TreeNode root, int targetSum) {25        this.k = targetSum;26        // The map stores <prefix sum, frequency>.27        // A prefix sum of 0 has a frequency of 1 to handle paths that start from the root.28        prefixSumCount.put(0L, 1);29        dfs(root, 0L);30        return count;31    }32 33    private void dfs(TreeNode node, long currentSum) {34        if (node == null) {35            return;36        }37 38        // 1. Update current path sum39        currentSum += node.val;40 41        // 2. Check if (currentSum - k) exists in the map42        // This is the core logic. If it exists, it means there's a path43        // from some ancestor to the current node that sums to k.44        count += prefixSumCount.getOrDefault(currentSum - k, 0);45 46        // 3. Update the map with the current prefix sum for descendant nodes47        prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);48 49        // 4. Recurse for children50        dfs(node.left, currentSum);51        dfs(node.right, currentSum);52 53        // 5. Backtrack: remove the current prefix sum from the map54        // This is crucial so that prefix sums from one branch don't affect sibling branches.55        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);56    }57}

Complexity

Time

O(N), where N is the number of nodes in the tree. Each node is visited exactly once, and the hash map operations (get, put) take O(1) time on average.

Space

O(H), where H is the height of the tree. This space is used by both the recursion stack and the hash map. In the worst case of a skewed tree, H = N, leading to O(N) space. For a balanced tree, H = log N, leading to O(log N) space.

Trade-offs

Pros

Highly efficient, with a linear time complexity as it traverses the tree only once.
Avoids redundant calculations by storing intermediate results (prefix sums) in a hash map.

Cons

The logic, particularly the concept of prefix sums in a tree and the necessity of backtracking, is more complex to understand.
Requires additional space for the hash map, which can be proportional to the height of the tree.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int PathSum ( TreeNode root , int targetSum ) { Dictionary < long , int > cnt = new Dictionary < long , int >(); int Dfs ( TreeNode node , long s ) { if ( node == null ) { return 0 ; } s += node . val ; int ans = cnt . GetValueOrDefault ( s - targetSum , 0 ); cnt [ s ] = cnt . GetValueOrDefault ( s , 0 ) + 1 ; ans += Dfs ( node . left , s ); ans += Dfs ( node . right , s ); cnt [ s ]--; return ans ; } cnt [ 0 ] = 1 ; return Dfs ( root , 0 ); } }

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Long , Integer > cnt = new HashMap <>(); private int targetSum ; public int pathSum ( TreeNode root , int targetSum ) { cnt . put ( 0L , 1 ); this . targetSum = targetSum ; return dfs ( root , 0 ); } private int dfs ( TreeNode node , long s ) { if ( node == null ) { return 0 ; } s += node . val ; int ans = cnt . getOrDefault ( s - targetSum , 0 ); cnt . merge ( s , 1 , Integer: : sum ); ans += dfs ( node . left , s ); ans += dfs ( node . right , s ); cnt . merge ( s , - 1 , Integer: : sum ); return ans ; } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number} */ var pathSum =2  function (root, targetSum) {3    const cnt = new Map();4    const dfs = (node, s) => {5      if (!node) {6        return 0;7      }8      s += node.val;9      let ans = cnt.get(s - targetSum) || 0;10      cnt.set(s, (cnt.get(s) || 0) + 1);11      ans += dfs(node.left, s);12      ans += dfs(node.right, s);13      cnt.set(s, cnt.get(s) - 1);14      return ans;15    };16    cnt.set(0, 1);17    return dfs(root, 0);18  };

1/** * Definition for a binary tree node. * 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 > cnt ; cnt [ 0 ] = 1 ; function < int ( TreeNode * , long ) > dfs = [ & ]( TreeNode * node , long s ) -> int { if ( ! node ) return 0 ; s += node -> val ; int ans = cnt [ s - targetSum ]; ++ cnt [ s ]; ans += dfs ( node -> left , s ) + dfs ( node -> right , s ); -- cnt [ s ]; return ans ; }; return dfs ( root , 0 ); } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def pathSum ( self , root : Optional [ TreeNode ], targetSum : int ) -> int : def dfs ( node , s ): if node is None : return 0 s += node . val ans = cnt [ s - targetSum ] cnt [ s ] += 1 ans += dfs ( node . left , s ) ans += dfs ( node . right , s ) cnt [ s ] -= 1 return ans cnt = Counter ({ 0 : 1 }) return dfs ( root , 0 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem