Problem statement
Given the root of a binary tree and an integer targetSum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example
Input:
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
targetSum = 22
Output: true
Explanation: 5 → 4 → 11 → 2 sums to 22.
Constraints (typical)
- Number of nodes is between 0 and a few thousand (varies by platform constraints).
- Node values can be negative, zero, or positive.
- targetSum is an integer.
Approach (simple English)
This problem asks whether there exists any path from root to leaf whose node values sum to targetSum. Two common approaches are simple and efficient:
Recursive depth-first search (preferred, simple)
- At each node, subtract the node’s value from
targetSumand then check its children with the remaining sum. - Base case: if node is null, return false.
- If node is a leaf (no left and right children), check if node.val equals the remaining
targetSum. - Otherwise, recursively check left or right subtree with
targetSum - node.val. - This runs in O(n) time where n is the number of nodes (we may visit each node once), and uses O(h) space for recursion stack where h is tree height.
Iterative DFS using a stack (explicit stack)
- Use a stack that stores pairs: (node, currentSumSoFar) or (node, remainingSum).
- Start with (root, root.val) or (root, targetSum – root.val).
- Pop nodes from stack; when visiting a node, if it’s a leaf, check the current path sum against target.
- Push children with updated path sum.
- This avoids recursion and makes control of stack explicit. Complexity O(n) time and O(h) space for the stack.
Breadth-first search is also possible (queue), but DFS is more natural for root-to-leaf path checks.
Which to pick
- Recursive solution is concise and clear; use it unless recursion depth is a concern.
- If the tree is very deep and recursion could overflow, prefer iterative approach.
Java code
Definition for tree node (LeetCode standard):
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
Recursive solution (clean and idiomatic):
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
return dfs(root, targetSum);
}
private boolean dfs(TreeNode node, int remaining) {
if (node == null) return false;
remaining -= node.val;
// if leaf, check if remaining is zero
if (node.left == null && node.right == null) {
return remaining == 0;
}
// otherwise check left or right subtree
return dfs(node.left, remaining) || dfs(node.right, remaining);
}
}
Iterative solution using explicit stack (node + remaining sum):
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
// Pair class to hold node and remaining sum
private static class Pair {
TreeNode node;
int remaining;
Pair(TreeNode n, int r) { node = n; remaining = r; }
}
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
Deque<Pair> stack = new ArrayDeque<>();
stack.push(new Pair(root, targetSum - root.val));
while (!stack.isEmpty()) {
Pair p = stack.pop();
TreeNode node = p.node;
int rem = p.remaining;
// if leaf and rem == 0 -> found a valid path
if (node.left == null && node.right == null && rem == 0) {
return true;
}
if (node.right != null) {
stack.push(new Pair(node.right, rem - node.right.val));
}
if (node.left != null) {
stack.push(new Pair(node.left, rem - node.left.val));
}
}
return false;
}
}
Alternative iterative style (stack stores node and current path sum so far):
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
private static class Pair {
TreeNode node;
int sumSoFar;
Pair(TreeNode n, int s) { node = n; sumSoFar = s; }
}
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
Deque<Pair> stack = new ArrayDeque<>();
stack.push(new Pair(root, root.val));
while (!stack.isEmpty()) {
Pair p = stack.pop();
TreeNode node = p.node;
int sum = p.sumSoFar;
if (node.left == null && node.right == null) {
if (sum == targetSum) return true;
}
if (node.right != null) {
stack.push(new Pair(node.right, sum + node.right.val));
}
if (node.left != null) {
stack.push(new Pair(node.left, sum + node.left.val));
}
}
return false;
}
}
Dry run (detailed step-by-step)
Use the example tree and targetSum = 22:
Tree:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
We will dry-run the recursive solution (dfs with remaining sum).
Initial call:hasPathSum(root=5, targetSum=22) -> calls dfs(5, 22)
- At node 5:
- remaining = 22 – 5 = 17
- node is not leaf
- check left: dfs(node 4, remaining 17)
- At node 4 (left of 5):
- remaining = 17 – 4 = 13
- not leaf
- check left: dfs(node 11, remaining 13)
- At node 11:
- remaining = 13 – 11 = 2
- not leaf
- check left: dfs(node 7, remaining 2)
- At node 7:
- remaining = 2 – 7 = -5
- node 7 is leaf (no children)
- remaining == 0? No (-5), so return false
- back to node 11, now check right child
- At node 2 (right of 11):
- remaining = 2 – 2 = 0
- node 2 is leaf
- remaining == 0? Yes => return true
- That true propagates back:
- dfs(11,13) returns true
- dfs(4,17) returns true
- dfs(5,22) returns true
- hasPathSum returns true
Thus result is true, and recursion unwinds.
Iterative stack dry run (stack stores node + remaining):
- Start: push (5, 22-5=17)
- Pop (5,17): push children (right 8 with rem 17-8=9), (left 4 with rem 17-4=13). Stack top is left 4.
- Pop (4,13): push children (11 with rem 13-11=2).
- Pop (11,2): push children (right 2 with rem 2-2=0), (left 7 with rem 2-7=-5). Stack top is left 7.
- Pop (7,-5): leaf but rem != 0, continue.
- Pop (2,0): leaf and rem == 0 -> return true.
Time and space complexity
Time complexity: O(n) where n is number of nodes. We potentially visit each node once.
Space complexity:
- Recursive solution: O(h) where h is the tree height (recursion stack).
- Iterative solution: O(h) for the explicit stack in the worst case. In the worst-case skewed tree h = n.
Edge cases and notes
- Empty tree (root == null) should return false.
- Single-node tree: check whether node.val == targetSum.
- Negative values: algorithm works the same for negative numbers.
- Very deep trees: recursive approach may cause stack overflow; use iterative approach if recursion depth is a concern.
- If you need to return the actual path instead of a boolean, you can carry a list of nodes/values along recursion or parent pointers in the iterative approach.