Skip to main content
Talentd

Path Sum III - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree23 min readAsked at: Amazon, Microsoft, Meta +8
Practice this problem

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

 

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].
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

Approach Overview

Problem 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 1: Using Depth-First Search (DFS) and Path Sum Calculation

This approach uses a combination of DFS and path sum calculation. For each node, calculate the sum of all paths that end at the current node. This is achieved recursively

This recursive solution calculates the number of paths that sum to the targetSum starting from each node. The function pathSumFrom checks both left and right paths recursively

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack.

Try this approach in the editor →

Approach 2: Using Hashmap to Store Prefix Sums

This approach leverages a hashmap to store cumulative sums and uses them to find paths that lead to the targetSum.

This solution uses a hashmap called prefix to capture the number of ways to obtain each cumulative sum that ends at a node. When a node is visited, the difference between the current cumulative sum and the target is used to check for matching sums encountered earlier.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n). Space Complexity: O(n), where n is the number of nodes in the tree.

Try this approach in the editor →

Approach 3: Hash Table + Prefix Sum + Recursion

We can use the idea of prefix sums to recursively traverse the binary tree while using a hash table cnt to count the occurrences of each prefix sum along the path from the root to the current node.

We design a recursive function dfs(node, s), where node represents the current node being traversed, and s represents the prefix sum along the path from the root to the current node. The return value of the function is the number of paths ending at node or its subtree nodes with a sum equal to targetSum. The final answer is dfs(root, 0).

The recursive process of dfs(node, s) is as follows:

  • If the current node node is null, return 0.
  • Calculate the prefix sum s along the path from the root to the current node.
  • Use cnt[s - targetSum] to represent the number of paths ending at the current node with a sum equal to targetSum. Here, cnt[s - targetSum] is the count of prefix sums equal to s - targetSum in cnt.
  • Increment the count of the prefix sum s by 1, i.e., cnt[s] = cnt[s] + 1.
  • Recursively traverse the left and right child nodes of the current node by calling dfs(node.left, s) and dfs(node.right, s), and add their return values.
  • After the return value is calculated, decrement the count of the prefix sum s by 1, i.e., cnt[s] = cnt[s] - 1.
  • Finally, return the result.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Depth-First Search (DFS) and Path Sum Calculation

Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack.

Using Hashmap to Store Prefix Sums

Time Complexity: O(n). Space Complexity: O(n), where n is the number of nodes in the tree.

Hash Table + Prefix Sum + Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS from Every NodeO(n^2)O(h)Simple implementation or when explaining baseline reasoning in interviews
Prefix Sum with Hash MapO(n)O(n)Best general solution; expected in interviews for optimal performance

Video Solution

Path Sum iii | LeetCode 437 | C++, Java, Python • Knowledge Center • 50,191 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Path Sum III easy or hard?
Path Sum III is generally classified as a medium-level problem. The brute-force DFS idea is easy to understand, but recognizing the prefix sum optimization and managing the hash map correctly during recursion requires stronger problem-solving experience.
How to solve Path Sum III in O(n)?
Traverse the tree using DFS while maintaining a running prefix sum from the root to the current node. Store counts of prefix sums in a hash map. At each node, check how many times prefixSum - targetSum has appeared, which represents valid paths ending at that node. Update the map during traversal and remove entries during backtracking.
What is the best approach for Path Sum III?
The most efficient approach uses a prefix sum hash map during a depth-first traversal. While exploring the tree, track the running sum and check if a previous prefix sum equal to currentSum - target exists. This allows you to count valid paths in O(n) time because each node is processed once.
Is Path Sum III asked at Google/Amazon/Meta?
Path Sum III is a common binary tree interview problem and has appeared in interviews at companies like Amazon, Meta, and Google. It tests understanding of DFS traversal, prefix sums, and how to maintain state across recursive tree paths.
What data structure is used in Path Sum III?
The optimal solution uses a hash map to store prefix sums and their frequencies during a depth-first traversal of the binary tree. The tree itself is explored using recursion or a DFS stack, while the hash map enables constant-time prefix sum lookups.
What is the time complexity of Path Sum III?
The brute-force DFS approach runs in O(n^2) time in the worst case because a DFS is started from every node. The optimized prefix sum method reduces this to O(n) by storing previously seen running sums in a hash map and performing constant-time lookups.
Path Sum III Python or Java solution approach?
Both Python and Java implementations follow the same pattern: perform DFS while tracking the current prefix sum and store counts in a hash map (dictionary in Python, HashMap in Java). Each node checks if prefixSum - target exists in the map to count valid paths.

Ready to solve this problem?

Practice Path Sum III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Univalue Path

Next

Path Sum