437. Path Sum III - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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

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

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def pathSumFrom(self, node, targetSum):
        if not node:
            return 0
        return (node.val == targetSum) + self.pathSumFrom(node.left, targetSum - node.val) + self.pathSumFrom(node.right, targetSum - node.val)

    def pathSum(self, root, targetSum):
        if not root:
            return 0
        return self.pathSumFrom(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

Java

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

public class Solution {
    private int dfs(TreeNode node, int sum) {
        if (node == null) return 0;
        return (node.val == sum ? 1 : 0) +
               dfs(node.left, sum - node.val) +
               dfs(node.right, sum - node.val);
    }

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
}

C++

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

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

class Solution {
public:
    int dfs(TreeNode* node, int sum) {
        if (!node) return 0;
        return (node->val == sum) + dfs(node->left, sum - node->val) + dfs(node->right, sum - node->val);
    }
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
};

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function pathSum(root, targetSum) {
    if (!root) return 0;

    function pathSumFrom(node, target) {
        if (!node) return 0;
        return (node.val === target ? 1 : 0) +
               pathSumFrom(node.left, target - node.val) +
               pathSumFrom(node.right, target - node.val);
    }

    return pathSumFrom(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}

#include <stdio.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int pathSumFrom(struct TreeNode* node, int targetSum) {
    if (!node) return 0;
    return (node->val == targetSum) +
           pathSumFrom(node->left, targetSum - node->val) +
           pathSumFrom(node->right, targetSum - node->val);
}

int pathSum(struct TreeNode* root, int targetSum) {
    if (!root) return 0;
    return pathSumFrom(root, targetSum) +
           pathSum(root->left, targetSum) +
           pathSum(root->right, targetSum);
}

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

public class Solution {
    private int PathSumFrom(TreeNode node, int targetSum) {
        if (node == null) return 0;
        return (node.val == targetSum ? 1 : 0) +
               PathSumFrom(node.left, targetSum - node.val) +
               PathSumFrom(node.right, targetSum - node.val);
    }

    public int PathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return PathSumFrom(root, targetSum) + PathSum(root.left, targetSum) + PathSum(root.right, targetSum);
    }
}

The Python solution employs recursion to check all possible paths from each node. It is a direct translation of the algorithms from other languages into Python.

Complexity

Time Complexity: O(n^2) in the worst case. Space Complexity: O(n).

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.

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def pathSum(self, root, sum):
        def dfs(node, curr_sum):
            if not node:
                return 0
            curr_sum += node.val
            res = prefix[curr_sum - sum]
            prefix[curr_sum] += 1
            res += dfs(node.left, curr_sum)
            res += dfs(node.right, curr_sum)
            prefix[curr_sum] -= 1
            return res

        from collections import defaultdict
        prefix = defaultdict(int)
        prefix[0] = 1
        return dfs(root, 0)

Java

import java.util.HashMap;

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

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);
        return helper(root, 0, sum, prefixSum);
    }

    private int helper(TreeNode node, int currSum, int target, HashMap<Integer, Integer> prefixSum) {
        if (node == null)
            return 0;

        currSum += node.val;
        int res = prefixSum.getOrDefault(currSum - target, 0);
        prefixSum.put(currSum, prefixSum.getOrDefault(currSum, 0) + 1);

        res += helper(node.left, currSum, target, prefixSum) +
               helper(node.right, currSum, target, prefixSum);
        
        prefixSum.put(currSum, prefixSum.get(currSum) - 1);

        return res;
    }
}

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.

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.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, targetSum: number): number {
    const cnt: Map<number, number> = new Map();
    const dfs = (node: TreeNode | null, s: number): number => {
        if (!node) {
            return 0;
        }
        s += node.val;
        let ans = cnt.get(s - targetSum) ?? 0;
        cnt.set(s, (cnt.get(s) ?? 0) + 1);
        ans += dfs(node.left, s);
        ans += dfs(node.right, s);
        cnt.set(s, (cnt.get(s) ?? 0) - 1);
        return ans;
    };
    cnt.set(0, 1);
    return dfs(root, 0);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
	cnt := map[int]int{0: 1}
	var dfs func(*TreeNode, int) int
	dfs = func(node *TreeNode, s int) int {
		if node == nil {
			return 0
		}
		s += node.Val
		ans := cnt[s-targetSum]
		cnt[s]++
		ans += dfs(node.Left, s) + dfs(node.Right, s)
		cnt[s]--
		return ans
	}
	return dfs(root, 0)
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

impl Solution {
    pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 {
        let mut cnt = HashMap::new();
        cnt.insert(0, 1);

        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, s: i64, target: i64, cnt: &mut HashMap<i64, i32>) -> i32 {
            if let Some(n) = node {
                let n = n.borrow();
                let s = s + n.val as i64;
                let ans = cnt.get(&(s - target)).copied().unwrap_or(0);
                *cnt.entry(s).or_insert(0) += 1;
                let ans = ans + dfs(n.left.clone(), s, target, cnt) + dfs(n.right.clone(), s, target, cnt);
                *cnt.get_mut(&s).unwrap() -= 1;
                ans
            } else {
                0
            }
        }

        dfs(root, 0, target_sum as i64, &mut cnt)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Depth-First Search (DFS) and Path Sum Calculation	Time Complexity: O(n^2) in the worst case. Space Complexity: O(n).
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	–

Complexity analysis

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

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.

Path Sum III solution and explanation

The problem

Approach overview

Approach 1: Using Depth-First Search (DFS) and Path Sum Calculation

Approach 2: Using Hashmap to Store Prefix Sums

Approach 3: Hash Table + Prefix Sum + Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Path Sum III solution and explanation

The problem

Approach overview

Approach 1: Using Depth-First Search (DFS) and Path Sum Calculation

Approach 2: Using Hashmap to Store Prefix Sums

Approach 3: Hash Table + Prefix Sum + Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems