Path Sum — Solution in Python, Java & C++
Path Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Microsoft.
Path Sum is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree and an integer targetSum, return true if some path from the root down to a leaf has node values adding up to exactly targetSum, and false otherwise. A leaf is a node with no children; an empty tree has no paths.
Example 1
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The path 5 → 4 → 11 → 2 sums to 22.
Example 2
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: The two root-to-leaf paths sum to 3 and 4.
Example 3
Input: root = [], targetSum = 0
Output: false
Explanation: An empty tree has no root-to-leaf path at all, not even one with sum 0.
Constraints
The number of nodes in the tree is in the range [0, 5000]-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Hints for Path Sum
Hint 1
Walking down from the root, keep track of how much of the target is still left.
Hint 2
Subtract each node's value as you descend; at a leaf, check whether exactly zero remains.
Hint 3
The path must end at a leaf — a node with one child is not an end point. Values may be negative, so you cannot stop early when the running sum passes the target.
How to solve Path Sum
Carry the remaining target down the tree. At a leaf the path is complete, and it qualifies exactly when the remainder equals the leaf's value.
Approach
- If
rootis null, returnfalse. - Let
rest = targetSum - root.val. - If
rootis a leaf, returnrest == 0. - Otherwise return
hasPathSum(root.left, rest) || hasPathSum(root.right, rest).
Why it works
Every root-to-leaf path is followed by exactly one chain of recursive calls, and along that chain rest equals the target minus the values seen so far. The null base case returns false, so a node with one child cannot end a path through its missing side.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- Returning
targetSum == 0at a null child lets a one-child node count as a leaf. - Negative values mean partial sums can overshoot and come back — no pruning on sign.
- An empty tree with
targetSum = 0isfalse.
Reference solution
Python
from typing import Optional
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
rest = targetSum - root.val
if root.left is None and root.right is None:
return rest == 0
return hasPathSum(root.left, rest) or hasPathSum(root.right, rest)Java
public static boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
int rest = targetSum - root.val;
if (root.left == null && root.right == null) return rest == 0;
return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
}C++
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
int rest = targetSum - root->val;
if (!root->left && !root->right) return rest == 0;
return hasPathSum(root->left, rest) || hasPathSum(root->right, rest);
}JavaScript
var hasPathSum = function(root, targetSum) {
if (root === null) return false;
var rest = targetSum - root.val;
if (root.left === null && root.right === null) return rest === 0;
return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)