Path Sum in Binary Tree
Problem
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum, and false otherwise.
- The number of nodes in the tree is in the range [0, 5000]
- −1000 ≤ Node.val ≤ 1000
- −1000 ≤ targetSum ≤ 1000
Example
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22trueThe algorithm explores paths starting from the root. For example, one path is 5 -> 4 -> 11 -> 2, which sums to 22. The recursion subtracts the current node's value from targetSum and explores left and right subtrees. When it reaches a leaf node, it checks if the remaining targetSum equals the leaf's value. If yes, it returns true, indicating a valid path exists. If no path matches, it returns false.
Approach
Straightforward Solution
A brute-force approach would explore all root-to-leaf paths, summing values along each path. This can be done with DFS, but without pruning, it explores all paths, which is acceptable here but can be inefficient for large trees.
Core Observation
The problem reduces to checking if any root-to-leaf path sums to targetSum. This naturally suggests a depth-first traversal where the targetSum is decremented by the current node's value at each step.
Path to Optimal
The key insight is to decrement targetSum as the recursion descends. When a leaf node is reached, checking if the remaining targetSum equals the leaf's value immediately confirms if a valid path exists. This pruning avoids unnecessary summations and leverages the recursive call stack to track path sums implicitly.
Optimal Approach
Use a recursive DFS that at each node subtracts the node's value from targetSum and recursively checks left and right children. If the node is a leaf, return whether the remaining targetSum equals the node's value. The recursion returns true if either subtree has a valid path, otherwise false.
Time
O(n)
Each node is visited once in the recursive traversal, resulting in linear time proportional to the number of nodes.
Space
O(h)
The recursion stack depth is at most the height of the tree, which is O(h). In the worst case (skewed tree), h can be O(n), but for balanced trees, h is O(log n).
Pattern Spotlight
DFS (Recursive State Exploration on Trees)
When searching for a path with a specific property in a tree, recursively reduce the problem by updating the target state and check conditions at leaf nodes, using the call stack to implicitly track the path.
Solution
| 1 | class Solution:
|
| 2 | def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
|
| 3 | if not root:
|
| 4 | return False
|
| 5 |
|
| 6 | if not root.left and not root.right:
|
| 7 | return root.val == targetSum
|
| 8 |
|
| 9 | return (self.hasPathSum(root.left, targetSum - root.val) or
|
| 10 | self.hasPathSum(root.right, targetSum - root.val)) |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public boolean hasPathSum(TreeNode root, int targetSum) { |
| 5 | if (root == null) { |
| 6 | return false; |
| 7 | } |
| 8 | if (root.left == null && root.right == null) { |
| 9 | return root.val == targetSum; |
| 10 | } |
| 11 | return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); |
| 12 | } |
| 13 | } |
| 1 | #include <iostream> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | bool hasPathSum(TreeNode* root, int targetSum) { |
| 8 | if (root == nullptr) { |
| 9 | return false; |
| 10 | } |
| 11 | if (root->left == nullptr && root->right == nullptr) { |
| 12 | return root->val == targetSum; |
| 13 | } |
| 14 | return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val); |
| 15 | } |
| 16 | }; |
| 1 | var hasPathSum = function(root, targetSum) { |
| 2 | if (root === null) { |
| 3 | return false; |
| 4 | } |
| 5 | if (root.left === null && root.right === null) { |
| 6 | return root.val === targetSum; |
| 7 | } |
| 8 | return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); |
| 9 | }; |
Step-by-Step Solution
Return False Immediately for Empty Tree
| 3 | if not root:
|
| 4 | return False
|
Objective
To handle the edge case where the input tree is empty, returning false since no path exists.
Key Insight
An empty tree has no root-to-leaf paths, so the answer must be false. This early return prevents unnecessary recursion and handles a critical boundary condition cleanly.
Interview Quick-Check
State & Boundaries
Check if the root is None to handle the empty tree edge case.
Common Pitfalls & Bugs
Failing to handle the empty tree can cause errors or incorrect results.
Check Leaf Node and Compare Value to Remaining TargetSum
| 6 | if not root.left and not root.right:
|
| 7 | return root.val == targetSum
|
Objective
To determine if the current node is a leaf and if its value matches the remaining targetSum, indicating a valid path.
Key Insight
Only leaf nodes represent complete root-to-leaf paths. By checking if the node has no children and if its value equals the remaining targetSum, the algorithm confirms whether the current path satisfies the sum condition without further recursion.
Interview Quick-Check
Core Logic
Return true if the current node is a leaf and its value equals the remaining targetSum.
State & Boundaries
Leaf nodes are identified by the absence of left and right children.
Common Pitfalls & Bugs
Checking the sum at non-leaf nodes can lead to incorrect true positives for incomplete paths.
Recursively Explore Left and Right Subtrees with Updated TargetSum
| 9 | return (self.hasPathSum(root.left, targetSum - root.val) or
|
| 10 | self.hasPathSum(root.right, targetSum - root.val)) |
Objective
To recursively check if either the left or right subtree contains a root-to-leaf path summing to the updated targetSum after subtracting the current node's value.
Key Insight
By subtracting the current node's value from targetSum, the problem reduces to finding a path in the subtrees that sums to the new target. Using logical OR ensures that if either subtree has a valid path, the function returns true, effectively propagating success up the call stack.
Interview Quick-Check
Core Logic
Recursively call hasPathSum on left and right children with targetSum reduced by current node's value, returning true if either subtree has a valid path.
State & Boundaries
The recursion terminates when leaf nodes are reached or when null nodes are encountered.
Common Pitfalls & Bugs
Forgetting to subtract the current node's value from targetSum leads to incorrect path sum calculations.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
return root.val == targetSumReturn whether the leaf node's value equals the remaining targetSum.
This comparison confirms if the current root-to-leaf path sums exactly to targetSum, which is the problem's success condition.
self.hasPathSum(root.right, targetSum - root.val))Recursively check the right subtree with updated targetSum and return true if either subtree has a valid path.
Using logical OR combines the results from both subtrees, ensuring the function returns true if any root-to-leaf path matches the target sum.
if not root.left and not root.right:Check if the current node is a leaf (no left or right child).
Identifying leaf nodes is essential because only root-to-leaf paths count; this condition ensures the sum is checked only at valid path endpoints.
return (self.hasPathSum(root.left, targetSum - root.val) orRecursively check the left subtree with updated targetSum.
Subtracting the current node's value from targetSum reduces the problem size, enabling the recursive search for a valid path in the left subtree.
if not root:Check if the root node is None (empty tree).
This early check handles the edge case of an empty tree, where no root-to-leaf path exists, allowing immediate return of false.
return FalseReturn false if the tree is empty.
Returning false here prevents further recursion and correctly signals that no path sum can be found in an empty tree.
Test Your Understanding
Why does the algorithm check for leaf nodes before comparing the remaining targetSum?
Because only root-to-leaf paths count, the sum must be checked at leaf nodes to ensure the path ends there; intermediate nodes do not represent complete paths.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Path Sum in Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Path Sum in Binary Tree drill