Watch 10 video solutions for Path Sum III, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Knowledge Center has 48,967 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[0, 1000].-109 <= Node.val <= 109-1000 <= targetSum <= 1000Problem Overview: You are given the root of a binary tree and a target sum. Count the number of paths where the sum of node values equals the target. A valid path must move downward (parent to child) but can start and end at any node in the tree.
Approach 1: Depth-First Search with Path Sum Calculation (Time: O(n^2), Space: O(h))
This approach treats every node as a potential starting point of a path. From each node, run a Depth-First Search that keeps subtracting the current node value from the remaining target. If the remaining value becomes zero, you found a valid path. After finishing paths starting from one node, recursively repeat the process for its left and right children.
The key idea is straightforward: explore every downward path starting at every node. In the worst case (a skewed tree), each DFS may traverse most of the tree, giving O(n^2) time complexity. Space complexity is O(h) for the recursion stack, where h is the tree height. This approach is simple to implement and works well for smaller trees, making it a good baseline solution when working with tree traversal problems.
Approach 2: Prefix Sum with Hash Map (Time: O(n), Space: O(n))
This optimized solution borrows the prefix sum idea commonly used in arrays and adapts it to a binary tree. While traversing the tree with DFS, maintain the running sum from the root to the current node. If the current prefix sum is curr and there was a previous prefix sum curr - target, then the nodes between them form a path that equals the target.
A hash map stores how many times each prefix sum has appeared along the current traversal path. Before exploring children, update the map with the current prefix sum. When backtracking, decrement the count so sibling branches do not reuse the same prefix path. Each node is processed once, and hash lookups take constant time, resulting in O(n) time and O(n) extra space.
Recommended for interviews: Start by explaining the DFS-from-every-node approach since it demonstrates clear understanding of tree traversal. Then move to the prefix sum optimization. Interviewers typically expect the O(n) prefix sum solution because it shows you can adapt array techniques to tree structures and manage state correctly during recursion.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS from Every Node | O(n^2) | O(h) | Simple implementation or when explaining baseline reasoning in interviews |
| Prefix Sum with Hash Map | O(n) | O(n) | Best general solution; expected in interviews for optimal performance |