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.

Tree: 5 -> [4 -> [11 -> [7, 2]], 8 -> [13, 4 -> [null, 1]]]
targetSum = 22  →  True   (5 + 4 + 11 + 2 = 22)
targetSum = 18  →  False

Try it

Python

Loading editor…

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([5,4,8,11,None,13,4,7,2,None,None,None,1]), 22)==True, "22 exists"
assert has_path_sum(build([5,4,8,11,None,13,4,7,2,None,None,None,1]), 18)==False, "18 does not exist"
assert has_path_sum(None, 0)==False, "empty tree"
assert has_path_sum(build([1,2]), 1)==False, "root-only path not leaf"
assert has_path_sum(build([1,2,3]), 4)==True, "path 1+3=4"

Hints (3)

Solution

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 [1, 2] with target 1: the root subtracts to 0 but has a left child, so it is not a leaf; it recurses into 2, where 0 - 2 = -2 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).