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.

Example 1

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.

Example 2

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

Solution: 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.

Java

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

Complexity Analysis

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