← Tree Traversal

Micro-Drill #209 — Path sum (root to leaf)

Tree Traversal Target: 10s

Subtract node value as you go down. At a leaf, check if remaining equals node value. Top-down DFS.

def hasPathSum(root, targetSum):
    if not root: return False
    if not root.left and not root.right:
        return root.val == targetSum
    return (hasPathSum(root.left, targetSum - root.val) or
            hasPathSum(root.right, targetSum - root.val))

Type it from memory. Go.

Practice Problems

• 112. Path Sum
• 113. Path Sum II

Related Coding Drills

• Drill #92 — Path sum Easy
• Drill #68 — Minimum path sum in grid Medium
• Drill #7 — Sliding window max sum of k elements Easy