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:
def 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.