Path Sum — Solution

Problem

Given a binary tree and an integer target, determine whether any root-to-leaf path exists where the node values sum to exactly the target. A leaf is a node with no children — paths must end at a leaf, not just any node.

Here is the tree [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1] with targetSum = 22:

[5,4,8,11,null,13,4,7,2,null,null,null,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.

Counter-example: targetSum = 5 with the same tree returns false — 5 alone hits the target value but 5 is not a leaf, so it does not count as a valid root-to-leaf path.

Intuition

At every node, the question simplifies: does any path from this node to a leaf sum to the remaining target? Subtract the current node's value and pass the updated remaining sum to each child. When you reach a leaf, check whether the remainder is exactly zero — that means the full path from the root summed to the original target.

Solution — Recursive DFS

Recurse into every root-to-leaf path, reducing the target by each node's value. Return true the moment any leaf path reaches exactly zero.

1. If the node is null, return false — an empty branch cannot complete a path.
2. Subtract the current node's value from the remaining target.
3. If this node is a leaf (no children) and the remainder is zero, return true.
4. Recurse into the left and right children with the updated remainder; return true if either succeeds.

1from typing import Optional
2
3class Solution:
4    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
5        if not root:
6            return False
7        
8        remaining = targetSum - root.val
9        
10        if not root.left and not root.right:  # reached a leaf
11            return remaining == 0
12        
13        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)

Time: O(n) — every node is visited once in the worst case (when no valid path exists).
Space: O(h) — the recursion stack depth equals the tree height; O(log n) for a balanced tree, O(n) for a skewed tree.

Complexity Summary

Common Mistakes

• Stopping at a non-leaf when the value matches: Checking remaining == 0 without first confirming not root.left and not root.right will return true at any internal node whose cumulative sum equals the target, even though the path hasn't reached a leaf.
• Returning false on a null node instead of false on a leaf: The null check is a base case for absent children, not for valid empty paths. An input of root = null should return false (no tree, no path), which this handles correctly.
• Integer overflow in C++: The problem constraints allow node values that are negative or positive; subtracting from targetSum is safe with standard int, but watch for very deep trees with large values.
• Forgetting that or short-circuits: In Python and Java, hasPathSum(left) or hasPathSum(right) stops as soon as the left subtree returns true — no need to explicitly guard the right recursive call, and no need for a manual boolean accumulator.
• Treating a single-node tree as a special case: It isn't one. A root with no children is a leaf, so the standard leaf check handles it without any extra branching.

Related Problems

• path-sum-ii — same DFS skeleton, but collect every valid root-to-leaf path instead of just checking existence
• path-sum-iii — harder variant where paths may start and end at any node, not just root to leaf
• sum-root-to-leaf-numbers — root-to-leaf paths treated as decimal digits; the DFS structure is identical
• binary-tree-maximum-path-sum — maximize a path sum over any path in the tree, not just root-to-leaf
• maximum-depth-of-binary-tree — same root-to-leaf DFS structure; count levels rather than accumulate a sum