[Easy] 112. 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.

Thinking Process

1. Backtracking Pattern: Subtract node value from target as we traverse

• Trees have no cycles — recursion is natural.
• Combine results from left and right subtrees at each node.
• Base case is usually null; height drives stack space.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Examples

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: There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Empty tree has no paths.

Constraints

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Common Mistakes

1. Empty tree: root = null, targetSum = 0 → return false
2. Single node: root = [1], targetSum = 1 → return true
3. Single node mismatch: root = [1], targetSum = 2 → return false
4. Negative values: root = [-2,null,-3], targetSum = -5 → return true
5. Zero sum: root = [1,-1], targetSum = 0 → return true (if path exists)

6. No valid path: root = [1,2,3], targetSum = 5 → return false

7. Checking at internal nodes: Validating sum before reaching leaf

   // WRONG:
   if (root->val == targetSum) return true; // ❌ Internal node check
   

8. Not handling empty tree: Forgetting null check
9. Wrong leaf check: Not checking both children are null
10. Accumulating instead of subtracting: Adding values instead of subtracting from target
11. Not using OR: Using AND instead of OR for subtree checks

Related Problems

• LC 112: Path Sum - This problem (check existence)
• LC 113: Path Sum II - Return all paths
• LC 437: Path Sum III - Count paths (any node to any node)
• LC 124: Binary Tree Maximum Path Sum - Maximum path sum
• LC 129: Sum Root to Leaf Numbers - Sum all root-to-leaf numbers
• LC 257: Binary Tree Paths - Return all root-to-leaf paths

Key Takeaways

1. Backtracking Pattern: Subtract node value from target as we traverse
2. Leaf Node Check: Only validate sum at leaf nodes (not internal nodes)
3. Early Termination: Return true immediately when valid path found
4. OR Logic: Only need one valid path, not all paths
5. Path Definition: Must be root-to-leaf (complete path)

References

• LC 112: Path Sum on LeetCode
• LeetCode Discuss — LC 112: Path Sum
• LeetCode Editorial (may require premium)

Template Reference

• Trees