Path Sum

Given a binary tree and a target sum, return true if there exists a root-to-leaf path whose values sum to the target.

Why this is worth learning

A root-to-leaf condition is stricter than reaching a target at any node. A zero remaining sum is meaningful only when the current node is a leaf.

Before coding: one-minute experiment

For root 5 with a single child 1, is target 5 a successful root-to-leaf sum?

Function signature

func HasPathSum(root *TreeNode, targetSum int) bool

Inputs / outputs

• root: root of the tree (may be nil).
• targetSum: target path sum.
• Return: true if a root-to-leaf path exists with sum targetSum.

Example

Tree: [5,4,8,11,null,13,4,7,2,null,null,null,1]
Target: 22
Output: true  // 5->4->11->2

Constraints

• 0 <= number of nodes <= 100_000
• Every mathematical root-to-node sum and every targetSum - prefixSum for a proper root-to-node prefix fits the target Go int. This bounds both running-sum and remaining-target implementations; unsupported inputs have no overflow-reporting contract.

Core idea (near-solution)

Enumerating each root-to-leaf path and summing it separately repeats additions along shared prefixes. Carry the shared work into recursion instead. The reference carries the amount still needed: when a node is chosen, subtract its value before asking a child to complete the remainder. Reaching the target at an internal node is insufficient because the path must end at a leaf. Arbitrary signed values also make sum-based pruning unsafe: a later negative node may repair an oversized prefix. A running-sum formulation is equivalent when its meaning and numeric bounds are kept consistent.

Invariant: At entry to a call, targetSum is the amount the current node-to-leaf path still needs to supply.

Algorithm (step-by-step)

1. If root is nil, return false.
2. If root is a leaf, return whether root.Val == targetSum.
3. Compute the remainder targetSum - root.Val.
4. Ask each child whether it can supply that remainder; return true if either can.

Correctness sketch

At a recursive call, target is the amount still required from the current node through a leaf. An empty subtree supplies no root-to-leaf path and returns false, even if target is zero. At a leaf, the only possible path contains that node, so compare its value with target. At an internal node, every eligible path must continue into one of its actual child subtrees; subtract the current value and ask whether either child can supply the remainder. Induction over subtrees proves both that every accepted path ends at a leaf and that every eligible path is considered.

Trace (hand walkthrough)

Example input:
Tree: [5,4,8,11,null,13,4,7,2,null,null,null,1]
Target: 22
Output: true  // 5->4->11->2

Walk:
- enter node 5 needing 22; children must supply 17
- enter node 4 needing 17; its child 11 must supply 13
- enter node 11 needing 13; its leaves must supply 2
- leaf 7 != 2 -> false; leaf 2 == 2 -> true
- return true through 11, 4, and 5

Pitfalls to avoid

• Accepting a path that ends at a non-leaf.
• Forgetting to handle negative values (do not prune incorrectly).

Debugging lens

Test negative values, an empty tree with target zero, and a target achieved only at an internal node. With negatives, pruning because a partial sum exceeds target is unsound.

Complexity

• Time: O(n).
• Extra space: O(h) recursion depth.

Implementation notes (Go)

• Passing remaining = targetSum - root.Val can simplify leaf checks.

Reconstruction checkpoint

A root 5 has only left child −2, which has only right child 4. Evaluate targets 5 and 7. Why is pruning as soon as a running sum exceeds the target unsafe?

Return to Binary Tree General · Module quiz