LeetCode #112 Easy

Path Sum

Does a root-to-leaf path exist whose values sum to targetSum?

treedfsrecursion

02

Intuition

Carry the remaining target down: each node subtracts its value and asks its children to cover the rest. At a leaf, the answer is exact: does the leaf's value equal what's left?

How to spot this pattern

Root-to-leaf questions are top-down recursion: carry a running value into the call rather than returning one up. Subtracting as you descend means the leaf test is a single comparison against zero-remaining. The tell for this family is any phrase like "a path from the root to a leaf" — the answer is decided at leaves, so the leaf definition is the part to get exactly right.

03

Approach

1

Subtract as you descend

hasPath(node, t) → at a leaf, check t == node.val; otherwise recurse with t − node.val.

2

Leaf check is strict

The path must END at a leaf — a null child alone doesn't qualify, which is why the leaf test comes before recursing.

3

OR over children

Either subtree may complete the path; short-circuit on the first success.

04

Solution & live demo

▶1class Solution:
▶2    def hasPathSum(self, root, targetSum):
▶3        if not root: return False
▶4        if not root.left and not root.right:
▶5            return targetSum == root.val
▶6        rest = targetSum - root.val
▶7        return (self.hasPathSum(root.left, rest)
▶8                or self.hasPathSum(root.right, rest))

05

Common pitfalls

Treating any node with a null child as a leaf

✗ Wrong

if not root.left or not root.right:
    return targetSum == root.val

✓ Right

if not root.left and not root.right:
    return targetSum == root.val

A node with one child is not a leaf — the path must keep going. With or, a half-empty node ends the path early and reports a sum for a path that never reached a leaf. A leaf has both children missing.

Returning true when the running sum hits zero mid-path

✗ Wrong

if targetSum == 0: return True

✓ Right

if not root.left and not root.right:
    return targetSum == root.val

The target must be met exactly at a leaf, not anywhere along the way. Values can be negative, so a path can hit the target mid-way and then move off it — stopping early answers a different question.

Returning true for an empty tree

✗ Wrong

if not root: return targetSum == 0

✓ Right

if not root: return False

A null node isn't a leaf and represents no path at all. Returning true there makes any node with one missing child succeed through its empty side, regardless of the values.

06

Edge cases

Empty tree

No root-to-leaf path exists → False even for target 0.

Negative values

No pruning on sign — the target can recover; explore fully.

07

Complexity

Time

O(n)

Space

O(h)

DFS, short-circuits on success.