Tree DFS carrying remaining sum: recurse with remaining_sum minus node value; return true when a leaf is reached with remaining_sum equal to zero.

Path Sum

Problem

Production health-check trees evaluate signal chains from sensors to a root aggregator. Each node has a weight, and a chain fires an alert only if the total weight from root to a specific sensor node equals a threshold. Given a binary tree root and an integer targetSum, return true if any root-to-leaf path has node values that sum to targetSum.

Example 1:

Input: root = [6,3,9,2,null,8,10,null,null,null,null,4], targetSum = 27
Output: true
Explanation: the path 6 -> 9 -> 8 -> 4 sums to 27.

Example 2:

Input: root = [6,3,9,2,null,8,10,null,null,null,null,4], targetSum = 21
Output: false

Constraints:

The number of nodes in the tree is in the range [0, 4000].
-500 <= Node.val <= 500
-500 <= targetSum <= 500

Try it

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    pass

Tests

def build(vals):
    if not vals:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    for i in range(len(nodes)):
        if nodes[i]:
            left_i, right_i = 2*i+1, 2*i+2
            if left_i < len(nodes): nodes[i].left = nodes[left_i]
            if right_i < len(nodes): nodes[i].right = nodes[right_i]
    return nodes[0]

assert has_path_sum(build([6,3,9,2,None,8,10,None,None,None,None,4]), 27)==True, "27 exists"
assert has_path_sum(build([6,3,9,2,None,8,10,None,None,None,None,4]), 21)==False, "21 does not exist"
assert has_path_sum(None, 0)==False, "empty tree"
assert has_path_sum(build([4,7]), 4)==False, "root-only path not leaf"
assert has_path_sum(build([5,1,9]), 14)==True, "path 5+9=14"

Hints (3)

Solution Breakdown

Approach: Tree DFS that carries the remaining sum downward and tests it at each leaf.

Instead of accumulating a running total upward, the recursion threads the target down: each call subtracts the current node's value from remaining_sum before going deeper, so by the time it reaches a leaf the question is simply "is what's left exactly 0?". The function has three branches. A None node returns False - it is not a path endpoint, just the absence of a child. After subtracting the node's value, a leaf (node.left is None and node.right is None) returns remaining_sum == 0, which is true only when the values along this single root-to-leaf path summed to the original target. Any internal node delegates with dfs(left, remaining_sum) or dfs(right, remaining_sum): a valid path exists if either subtree contains one, and or short-circuits so the moment a match is found the rest of the tree is skipped.

Checking specifically for a leaf, not just remaining_sum == 0, is essential - stopping at an internal node that happens to hit zero would accept a partial path. Trace [4, 7] with target 4: the root subtracts to 0 but has a left child, so it is not a leaf; it recurses into 7, where 0 - 7 = -7 at a leaf, returning False.

Edge cases: An empty tree (None root) returns False. Negative node values work because remaining_sum may swing positive or negative along a path before the leaf comparison.

Complexity: O(n) time, O(h) space - every node is visited once, and the call stack holds at most the tree's height (O(log n) balanced, O(n) skewed).

Path Sum

Problem

Solution Breakdown

Discussion