437. Path Sum III¶
Edited by Charles
Medium · Python · Binary Tree
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
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.
Original study notes follow, including intermediate snippets and earlier attempts.
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.
Important requirements:
- The path does not need to start from the root.
- The path does not need to end at a leaf.
- The path must move downward, from parent to child.
Example¶
There are three valid paths:
Therefore:
The key difficulty is:
A valid path can start from any node.
Therefore, we divide the problem into two parts:
pathSum()
↓
Choose every node as a possible starting point
backtrack()
↓
Once the starting point is fixed,
search all downward paths starting from it
So we use two recursive functions with different responsibilities.
Define:
as:
The number of valid paths that start exactly from
nodeand go downward with sum equal totargetSum.
For example:
Suppose:
If we call:
we only consider paths starting from 5:
Therefore:
Inside backtrack():
Why?
Because targetSum represents the remaining sum we still need.
If:
then the path from the original starting node to the current node has exactly the required sum.
Therefore, we find one valid path:
After using node.val, the remaining target becomes:
So we recursively search both children:
Therefore:
return (
count
+ self.backtrack(node.left, targetSum - node.val)
+ self.backtrack(node.right, targetSum - node.val)
)
This means:
number of valid paths
=
path ending at current node
+
valid paths continuing into left subtree
+
valid paths continuing into right subtree
backtrack() has one limitation:
It only searches paths starting from the node passed into it.
For example:
Suppose:
There is a valid path:
If we only call:
we only consider:
We will never consider:
because its starting point is 3, not 10.
Therefore, we need another recursion to let every node become a starting point.
That is the purpose of:
For the current root:
counts all valid paths starting exactly from root.
But paths can also start somewhere inside the left subtree:
or somewhere inside the right subtree:
Therefore:
return (
self.backtrack(root, targetSum)
+ self.pathSum(root.left, targetSum)
+ self.pathSum(root.right, targetSum)
)
This is the most important formula of this solution.
This distinction is extremely important.
Suppose:
If we write:
then we only consider paths starting exactly from 5:
We still do not consider 3 as a new independent starting point.
But:
means:
So eventually:
will all become starting nodes.
Therefore:
while:
This solution can be understood as two levels of DFS.
Outer DFS — pathSum()¶
Purpose:
Conceptually:
root
/ \
node node
/ \
node node
↓
Try root as start
Try every node in left subtree as start
Try every node in right subtree as start
Inner DFS — backtrack()¶
Purpose:
For example:
backtrack(start) explores:
It never moves upward.
Consider:
First:
Starting from 5¶
Call:
At 5:
Continue with:
Go left to 3:
Found:
Go right to 2:
Remaining:
Go to 1:
Found:
Therefore:
Then pathSum() recursively considers:
This guarantees that every possible downward path is considered.
In a traditional backtracking problem, we often write:
But this problem only asks for:
It does not ask us to return the actual paths.
Therefore, we do not need to maintain a path list.
Instead, we keep track of the remaining target:
Also, targetSum is an integer.
Each recursive call receives its own integer value, so we do not need to manually restore it with a pop() operation.
pathSum(root)
│
├── backtrack(root)
│ │
│ └── Count all valid paths
│ STARTING from root
│
├── pathSum(root.left)
│ │
│ └── Let every node in the left subtree
│ become a new starting point
│
└── pathSum(root.right)
│
└── Let every node in the right subtree
become a new starting point
So:
and:
Outer Recursion¶
Meaning:
paths starting at root
+
paths starting somewhere in left subtree
+
paths starting somewhere in right subtree
Inner Recursion¶
backtrack(node, target)
=
current valid path
+ backtrack(node.left, target - node.val)
+ backtrack(node.right, target - node.val)
Meaning:
Time Complexity¶
In the worst case:
Why?
pathSum() may use every node as a starting point.
For every starting point, backtrack() may visit many nodes below it.
For a skewed tree:
we may perform approximately:
operations.
Therefore:
Space Complexity¶
The recursion depth depends on the height of the tree:
Worst case for a skewed tree:
The most important idea is to separate two responsibilities:
and:
So remember:
And the key code is:
return (
self.backtrack(root, targetSum)
+ self.pathSum(root.left, targetSum)
+ self.pathSum(root.right, targetSum)
)
Do not replace the last two calls with:
because that would only make the immediate children new starting points and would miss paths starting from deeper nodes.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | September 14, 2026 |
Python solution¶
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
if not root:
return 0
return (
self.backtrack(root, targetSum)
+ self.pathSum(root.left, targetSum)
+ self.pathSum(root.right, targetSum)
)
def backtrack(self, node, targetSum):
if not node:
return 0
count = 0
if node.val == targetSum:
count += 1
return (
count
+ self.backtrack(node.left, targetSum - node.val)
+ self.backtrack(node.right, targetSum - node.val)
)