Path Sum in a Binary Tree: A Step-by-Step Interview Walkthrough
Path Sum in a Binary Tree is a deceptively simple-looking problem that interviewers use as a reading comprehension test as much as an algorithm test. The problem statement contains specific constraints that, if misread, lead candidates to solve a harder problem than the one asked. Candidates who skim the requirements often write algorithms that handle "any path" or "any node to any node," which is significantly more complex and earns no extra credit. Candidates who pause at the words "root-to-leaf" and pin down exactly what counts as a valid endpoint solve it in eight lines of recursion. The signal here isn't whether you can write tree DFS — it's whether you can read constraints precisely and solve the right problem.
Path-based queries on trees show up everywhere systems care about cumulative properties along hierarchical chains. File system tools sum the sizes of files along a directory path. Compilers walk inheritance chains to compute total memory layouts. Permission systems aggregate access rights from root to a specific resource. Decision-tree machine learning models evaluate cumulative scores from root to leaf. Whenever a hierarchy has numeric weights and we want to check whether some specific endpoint satisfies a sum condition, the same accumulate-and-check-at-leaf pattern applies.
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.
Return true if such a path exists, false otherwise.
Example:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1For targetSum = 22, the answer is true (path: 5 → 4 → 11 → 2).
1. Clarify Requirements Before Jumping Into Code
Let's start by restating the problem in our own words and ask the kinds of questions that would change our approach.
Input: the root of a binary tree (may be null) and an integer targetSum.
Output: a boolean — true if there exists a root-to-leaf path with the given sum.
Details to clarify:
What counts as a leaf? A node with no children — both left and right are null.
Does the path have to start at the root? Yes — this is critical. Paths starting from internal nodes don't count.
Does the path have to end at a leaf? Yes — partial paths ending at internal nodes don't count, even if their sum equals targetSum.
Can node values be negative? Yes — which means we can't prune branches based on running sums alone.
Can targetSum be negative? Yes.
What do we return for an empty tree? false — there are no paths at all, so no path can satisfy the target.
The thing to flag is the exact definition of a valid path: root → leaf, not partial, not internal-to-internal. This is the trap. Candidates who solve "any contiguous downward path" or "any path from any node" are solving a harder, different problem.
2. Identify the Category of the Question
A few signals jump out:
The input is a tree.
We're walking from a fixed starting point (the root) to a constrained endpoint (any leaf).
We're accumulating a value as we descend.
That combination — fixed start, constrained endpoint, accumulating value, boolean answer — places this in the DFS with running state family. Same shape as "Path Sum II" (where we collect all valid paths), "Sum Root to Leaf Numbers," and many other root-to-leaf accumulation problems. The core technique is to propagate a running value downward through the recursion and check it at the leaves.
3. Brute Force Solution
The most obvious approach is to enumerate every root-to-leaf path, compute each path's sum, and return true if any matches.
List<List<Integer>> allPaths = collectAllPaths(root);
for (List<Integer> path : allPaths) {
int sum = 0;
for (int v : path) sum += v;
if (sum == targetSum) return true;
}
return false;This is technically correct. But notice what it's doing: it builds every path in memory before checking any of them. For a tree with many leaves, that's a lot of wasted storage. And the algorithm has no way to stop early — it always computes all paths before checking.
The brute force teaches us two things worth keeping. First, we don't actually need to remember the paths — we only need their sums. Second, we can stop as soon as we find one match; there's no need to enumerate further. These two observations point to a leaner approach.
4. Brainstorm More Solutions
Step 1: What information do we actually need at each node?
Let's think about the minimum amount of information we need to maintain as we descend the tree. At a leaf, we need to know whether the cumulative sum from the root equals targetSum. Everywhere else, we just need to keep that running sum updated.
So as we walk down from the root, we carry one piece of state: the sum of values we've encountered so far. When we visit a node, we add its value to the running sum. When we hit a leaf, we compare the running sum against the target.
To implement that, we need to pass along two variables - the targetSum and our runningSum. Is there any way to streamline that a bit so we don't need both variables? What if instead of adding values to a running sum and comparing to targetSum at the end, we can subtract values from targetSum as we go and check whether we hit zero at the leaf. The two are mathematically equivalent, but the subtraction version is slightly nicer because the goal stays constant (always "reach zero") instead of needing two parameters everywhere.
Step 2: Translate the idea into recursion
Define hasPathSum(node, remaining) returning true if there's a path from node down to some leaf whose values sum to remaining.
The recursive structure:
Base case (null node): return false. No path goes through a null node; this case appears when we try to recurse into a missing child of an internal node.
At a node: subtract the current value from remaining.
If this is a leaf: return whether remaining == 0 after the subtraction.
Otherwise: the question becomes "does the left subtree or the right subtree contain a valid path?" Return true if either does.
hasPathSum(node, remaining):
if node is null:
return false
remaining -= node.val
if node is a leaf:
return remaining == 0
return hasPathSum(node.left, remaining) OR hasPathSum(node.right, remaining)The recursion mirrors the problem definition almost exactly. We descend the tree, subtract as we go, and check at the boundary.
Step 3: A subtle correctness trap — treating null as a leaf
There's one detail that can trip you up the first time you write this algorithm. The intuitive base case for hitting a null is return remaining == 0 — after all, we've reached "the end of a path," and if the running sum landed at zero, isn't that a match?
hasPathSum(node, remaining):
if node is null:
return remaining == 0 # BUG
...Unfortunately, that doesn't work. A null isn't a path endpoint; it's the absence of a node. The problem requires paths ending at real leaves, which are nodes with no children — not nodes with one missing child.
Consider a node with one child with targetSum = 5:
5
\
3The only real root-to-leaf path is 5 → 3 = 8, which doesn't match, so the correct answer is false. But with the buggy base case return remaining == 0 at null, we'd:
subtract 5 at the root,
recurse into the missing left child,
see remaining == 0,
and incorrectly return true.
The bug treats the absent left child as if it were a valid endpoint, when really the only valid endpoint is the leaf 3.
The fix is the version we already have: null returns false unconditionally, and remaining == 0 is checked only at actual leaves (both children null). That keeps absent positions out of the answer entirely and forces every "match" to come from a real leaf. This is one of those corner-case distinctions that separates code that passes the obvious tests from code that handles one-child trees correctly.
Step 4: An iterative alternative for stack-safety
The recursive solution is clean, but for deeply skewed trees the recursion depth equals the tree's height, which can blow the call stack on adversarial inputs. As is often the case with recursive solutions, we can rewrite our algorithm iteratively using an explicit stack, which moves the storage from the call stack to the heap and removes the overflow risk.
The trick is recognizing that the recursion was carrying two pieces of state at each call: the node we're visiting and the remaining sum at that point. To unroll the recursion, we need to keep those two pieces of state together as we walk the tree. The natural way is a stack of (node, remaining) pairs. We push the root with the initial targetSum, then repeatedly pop a pair, check whether we've found a valid leaf, and push the children with the updated remaining if not.
public static boolean hasPathSumIterative(TreeNode root, int targetSum) {
if (root == null) return false;
Deque<TreeNode> nodes = new ArrayDeque<>();
Deque<Integer> remainings = new ArrayDeque<>();
nodes.push(root);
remainings.push(targetSum);
while (!nodes.isEmpty()) {
TreeNode node = nodes.pop();
int remaining = remainings.pop() - node.val;
// Leaf check — only here do we compare against zero
if (node.left == null && node.right == null && remaining == 0) {
return true;
}
// Push children with the updated remaining
if (node.right != null) {
nodes.push(node.right);
remainings.push(remaining);
}
if (node.left != null) {
nodes.push(node.left);
remainings.push(remaining);
}
}
return false;
}Two details worth noting.
First, we never push null children onto the stack — the recursive version's "null returns false" check is replaced here by simply not enqueueing absent children in the first place. That's the iterative analog of the null guard from Step 3: instead of recursing into nothing and then bailing out, we never recurse there at all.
Second, we use two parallel stacks (one for nodes, one for remaining sums) because Java doesn't have built-in tuples. In a language with pairs or tuples, you'd combine them into a single stack of pairs; the logic is identical.
The complexity is the same as the recursive version — O(n) time and O(h) space — but the space now lives on the heap. For interview purposes, I'd lead with the recursive version because it's more readable, and mention the iterative one as the answer to "what if the tree could be deep enough to overflow the stack?"
Step 5: Walk through the example
Let's verify on:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1Target = 22. Trace hasPathSum(5, 22):
At 5: subtract 5, remaining = 17. Not a leaf, recurse.
Left: hasPathSum(4, 17).
At 4: subtract 4, remaining = 13. Not a leaf, recurse.
Left: hasPathSum(11, 13).
At 11: subtract 11, remaining = 2. Not a leaf, recurse.
Left: hasPathSum(7, 2). At 7: subtract 7, remaining = -5. Leaf. Return -5 == 0 → false.
Right: hasPathSum(2, 2). At 2: subtract 2, remaining = 0. Leaf. Return 0 == 0 → true.
Returns true.
Whole thing returns true.
The recursion correctly identifies the path 5 → 4 → 11 → 2 summing to 22, and short-circuits without checking the right subtree once it has an answer.
Step 6: Complexity
The DFS visits each node at most once and does O(1) work per visit. Total time is O(n).
Space is O(h) for the recursion stack, where h is the tree's height. For balanced trees this is O(log n); for skewed trees, O(n).
This is fundamentally better than the brute force's O(n) space for path storage, and it benefits from short-circuit evaluation — the || operator stops evaluating as soon as the left side returns true, so we never explore the right subtree if the left already found a match.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Enumerate all paths, then check sums | O(n) | O(n × h) | Never — stores too much, no early exit |
DFS with running sum. Short circuit when we find a correct answer | O(n) | O(h) | The best solution to this problem |
Iterative DFS with explicit stack | O(n) | O(h) | If recursion depth is a concern on adversarial inputs |
The recursive DFS with subtraction is the standard answer. It's compact, correct, and short-circuits naturally through the || operator.
6. Pseudocode
hasPathSum(root, targetSum):
if root is null:
return false
return dfs(root, targetSum)
dfs(node, remaining):
if node is null:
return false
remaining -= node.val
if node is a leaf: # both children are null
return remaining == 0
return dfs(node.left, remaining) OR dfs(node.right, remaining)7. Edge Cases
Things to verify before claiming we're done:
Empty tree (null root) → return false immediately. ✓
Single-node tree where root.val == targetSum → at the leaf, remaining == 0, returns true. ✓
Single-node tree where root.val != targetSum → returns false. ✓
Tree with a node that has one child → the null child doesn't get treated as a leaf because the null check returns false. ✓
Negative node values or negative targetSum → the subtraction handles signs correctly; no special casing needed.
A valid sum exists but only at an internal node (not at a leaf) → returns false, because the problem requires root-to-leaf paths specifically. The leaf check rejects mid-tree matches.
The two checks at the top of dfs — null first, then leaf — handle every shape cleanly. Mixing up their order or merging them into "if no children, check remaining" creates the one-child bug from Step 4.
8. Full Code
public class PathSum {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return dfs(root, targetSum);
}
private static boolean dfs(TreeNode node, int remaining) {
// Null guard: a missing child is NOT a leaf.
// Returning false here prevents us from treating
// absent nodes as valid path endpoints.
if (node == null) {
return false;
}
remaining -= node.val;
// Only check the target at an actual leaf — a real node
// with no children.
if (node.left == null && node.right == null) {
return remaining == 0;
}
// Short-circuit: the OR stops evaluating the right
// subtree once the left has found a valid path.
return dfs(node.left, remaining)
|| dfs(node.right, remaining);
}
}9. Test the Code
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);
System.out.println(hasPathSum(root, 22)); // true (5 → 4 → 11 → 2)
System.out.println(hasPathSum(root, 26)); // true (5 → 8 → 13)
System.out.println(hasPathSum(root, 18)); // false (no root-to-leaf matches)
// Empty tree
System.out.println(hasPathSum(null, 0)); // false
// Single node matching target
System.out.println(hasPathSum(new TreeNode(7), 7)); // true
// Single node not matching target
System.out.println(hasPathSum(new TreeNode(7), 0)); // false
// Tree with a one-child internal node — common bug trigger
TreeNode oneChild = new TreeNode(1);
oneChild.left = new TreeNode(2);
System.out.println(hasPathSum(oneChild, 1)); // false (only path is 1→2 = 3, not 1)
System.out.println(hasPathSum(oneChild, 3)); // true (1→2 = 3)
// Negative values
TreeNode neg = new TreeNode(-2);
neg.right = new TreeNode(-3);
System.out.println(hasPathSum(neg, -5)); // true (-2 + -3 = -5)These hit the meaningful cases: valid matches in different branches, a non-match, the empty tree, single-node trees in both directions, the one-child tree (which is the classic bug trigger), and negative values to verify the arithmetic.
10. Key Lessons
Read constraints carefully before designing the algorithm. "Root-to-leaf" is a specific path definition; solving "any path" or "any downward path" is a different problem that requires more machinery. The candidates who get tripped up on Path Sum are usually solving a harder version of the problem than the one asked.
Carry state down through recursion instead of building it up afterward. Subtracting from a running target and checking against zero at the leaf is cleaner than accumulating a sum and comparing to a target everywhere. Whenever you can transform "build, then compare" into "compare as you go," the resulting code is usually simpler.
A "leaf" is a real node with no children. A null is the absence of a node, not a node itself. Conflating the two — treating null as a leaf — is a classic source of off-by-one bugs in tree problems. Always check for null first, then check for leaf-ness separately.
Short-circuit evaluation (|| in most languages) gives you "early exit" for free in boolean tree problems. As soon as the left subtree returns true, the right subtree is never explored. Use this naturally; you don't need explicit "found" flags.
For boolean queries on trees, the recursion structure is almost always: "does this subtree contain a valid X?" combined with || across children. Recognize this pattern, and a whole family of similar problems — "does a path exist," "is there a node satisfying Y," "can we reach a state Z from here" — start to feel mechanical.
The thing that makes Path Sum click is reading the problem statement precisely and noticing that "root-to-leaf" is doing real work in the definition. Once you train yourself to pause on the constraint words rather than skim past them, you'll consistently solve the right problem instead of an unnecessarily harder one. That habit alone will save you across the next dozen tree problems you encounter.
Good Luck and Happy Coding!
Comments