Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

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 22.

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: Available paths: 1→2 (sum 3) and 1→3 (sum 4). Neither equals 5.

Constraints:

0 <= Number of nodes <= 5000
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Solution — Recursive DFS (Subtraction)
Complexity Analysis

Recursive DFS (Subtraction)

Instead of accumulating a running sum, we subtract each node's value from the target as we descend. At a leaf node, if the remaining value equals the leaf's value (i.e., the remainder after subtraction is 0 at that leaf), we found a valid path.

Algorithm:

Base case: if root == null, return false.
At each node, subtract the node's value from targetSum.
If the node is a leaf and the remaining sum is 0, return true.
Recurse on left and right subtrees; return true if either returns true.

public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; targetSum -= root.val; // leaf node check if (root.left == null && root.right == null) { return targetSum == 0; } return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum); }

Trace through Example 1: targetSum = 22, path 5→4→11→2

Node	targetSum after subtraction
5	22 - 5 = 17
4	17 - 4 = 13
11	13 - 11 = 2
2 (leaf)	2 - 2 = 0 → return true

Time: O(n) — in the worst case every node is visited.
Space: O(h) — recursion stack depth equals the tree height h.

Constraints:

Contents

Algorithm:

Trace through Example 1: targetSum = 22, path 5→4→11→2