Path Sum Pattern

Path problems ask questions about routes from one node to another. The simplest form: does a root-to-leaf path with a given sum exist?

The recursive approach passes the remaining sum down:

function hasPathSum(root, targetSum):
    if root == null:
        return false
    if root.left == null and root.right == null:
        return root.val == targetSum
    remaining = targetSum - root.val
    return (hasPathSum(root.left, remaining) or
        hasPathSum(root.right, remaining))

Check for leaf explicitly: a node with no children. Don't count null as a path endpoint.

This pattern extends to: finding all paths, finding maximum path sum, counting paths with given sum.