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.

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

Core idea (near-solution)

DFS while keeping a running sum (or remaining sum). Only leaf nodes can complete a valid path.

Invariant: sum represents the sum from the root down to the current node.

Algorithm (step-by-step)

1. If root is nil, return false.
2. Add root.Val to the running sum.
3. If root is a leaf, return whether the sum equals targetSum.
4. Recurse on left or right; return true if either returns true.

Correctness sketch

• Invariant: sum represents the sum from the root down to the current node.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

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:
- path 5->4->11->2 sums to 22 -> true
- other root-to-leaf paths (5->8->13=26, 5->8->4->1=18) fail

Pitfalls to avoid

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

Complexity

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

Implementation notes (Go)

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