LeetCode 112: Path Sum

Problem Restatement

We are given the root of a binary tree and an integer targetSum.

We need to return True if the tree has at least one root-to-leaf path whose node values add up to targetSum. A leaf is a node with no children. If no such path exists, return False. The official problem uses this same root-to-leaf path requirement.

For this tree:

        5
      /   \
     4     8
    /     / \
   11    13  4
  /  \        \
 7    2        1

and:

targetSum = 22

There is a valid path:

5 -> 4 -> 11 -> 2

The sum is:

5 + 4 + 11 + 2 = 22

So the answer is:

True

Input and Output

LeetCode gives the TreeNode class:

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

The function shape is:

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        ...

Examples

Consider:

        5
      /   \
     4     8
    /     / \
   11    13  4
  /  \        \
 7    2        1

with:

targetSum = 22

One root-to-leaf path is:

5 -> 4 -> 11 -> 2

Its sum is:

22

So the answer is:

True

Now consider:

    1
   / \
  2   3

with:

targetSum = 5

The root-to-leaf paths are:

1 -> 2 = 3
1 -> 3 = 4

No root-to-leaf path sums to 5, so the answer is:

False

For an empty tree:

root = None
targetSum = 0

The answer is:

False

An empty tree has no root-to-leaf paths.

First Thought: Try Every Root-to-Leaf Path

The direct idea is to explore every path from the root down to a leaf.

For each path, compute the sum of its node values.

If any path sum equals targetSum, return True.

This naturally suggests depth-first search, because DFS follows one path downward before trying another path.

Key Insight

Instead of storing the whole path, we only need the remaining sum.

At each node, subtract the current node value from targetSum.

For example, suppose:

targetSum = 22

At the root 5, the remaining sum becomes:

22 - 5 = 17

At node 4, it becomes:

17 - 4 = 13

At node 11, it becomes:

13 - 11 = 2

At leaf node 2, the remaining sum becomes 0.

So a valid path exists.

The important check happens only at a leaf. A partial path that sums to the target before reaching a leaf does not count.

Algorithm

If root is None, return False.

Otherwise:

1. If the current node is a leaf, check whether its value equals targetSum.
2. Subtract the current node’s value from targetSum.
3. Recursively check the left subtree.
4. Recursively check the right subtree.
5. Return True if either subtree has a valid path.

The recursive rule is:

hasPathSum(node.left, targetSum - node.val)
or
hasPathSum(node.right, targetSum - node.val)

Correctness

The algorithm explores every root-to-leaf path.

At each recursive call, targetSum represents the sum still needed from the current node down to a leaf.

If the current node is None, there is no path, so returning False is correct.

If the current node is a leaf, the current path is complete. The path is valid exactly when the leaf value equals the remaining target. Therefore, the algorithm returns True exactly for a leaf that completes a valid root-to-leaf sum.

If the current node is not a leaf, any valid path must continue through either the left child or the right child. After subtracting the current node value, the recursive calls check both possible continuations. If either side returns True, a valid path exists.

Therefore, the algorithm returns True exactly when the tree contains at least one root-to-leaf path whose values sum to targetSum.

Complexity

Here, n is the number of nodes and h is the height of the tree.

For a balanced tree, h = O(log n).

For a skewed tree, h = O(n).

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None:
            return root.val == targetSum

        remaining = targetSum - root.val

        return (
            self.hasPathSum(root.left, remaining)
            or self.hasPathSum(root.right, remaining)
        )

Code Explanation

The empty tree has no valid path:

if root is None:
    return False

Check whether the current node is a leaf:

if root.left is None and root.right is None:

If it is a leaf, the path ends here. The path is valid only when the leaf value equals the remaining target:

return root.val == targetSum

For a non-leaf node, subtract the current value:

remaining = targetSum - root.val

Then check both subtrees:

return (
    self.hasPathSum(root.left, remaining)
    or self.hasPathSum(root.right, remaining)
)

The or means one valid path is enough.

Testing

from typing import Optional

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

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None:
            return root.val == targetSum

        remaining = targetSum - root.val

        return (
            self.hasPathSum(root.left, remaining)
            or self.hasPathSum(root.right, remaining)
        )

def run_tests():
    s = Solution()

    root1 = TreeNode(
        5,
        TreeNode(
            4,
            TreeNode(11, TreeNode(7), TreeNode(2)),
            None,
        ),
        TreeNode(
            8,
            TreeNode(13),
            TreeNode(4, None, TreeNode(1)),
        ),
    )
    assert s.hasPathSum(root1, 22) is True

    root2 = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.hasPathSum(root2, 5) is False

    root3 = None
    assert s.hasPathSum(root3, 0) is False

    root4 = TreeNode(1)
    assert s.hasPathSum(root4, 1) is True
    assert s.hasPathSum(root4, 0) is False

    root5 = TreeNode(1, TreeNode(2), None)
    assert s.hasPathSum(root5, 1) is False
    assert s.hasPathSum(root5, 3) is True

    root6 = TreeNode(-2, None, TreeNode(-3))
    assert s.hasPathSum(root6, -5) is True

    print("all tests passed")

run_tests()

Test meaning: