Path Sum

Difficulty: Easy

Problem

Given the root of a binary tree and an integer targetSum, return true if the tree has any root-to-leaf path such that adding up all the values along the path equals targetSum. Important: the path must start at the ROOT and end at a LEAF — a node with no children.

Example

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The path 5 → 4 → 11 → 2 sums to 5 + 4 + 11 + 2 = 22, and node 2 is a leaf. Found!

Brute-force approach

There is no meaningful brute force vs optimal split — the recursive remaining-sum walk IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: Think 'how much is LEFT?' instead of 'how much so far?'. One shrinking number rides down the recursion, and leaves give an instant yes/no.

Walk down the tree carrying the amount still needed. Each node subtracts its own value; a leaf succeeds if exactly 0 remains.

Steps

1. Base case: null has no paths — return false
2. Compute remaining = targetSum − node.val
3. If the node is a leaf, return remaining == 0
4. Otherwise ask both children with the new remaining, combined with OR

Time complexity: O(n) · Space complexity: O(h) where h = height of tree