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.

Examples

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
          5
         / \
        4   8
       /   / \
      11  13  4
     / \       \
    7   2       1
Output: true
Explanation: Path 5 → 4 → 11 → 2 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false

Example 3:

Input: root = [], targetSum = 0
Output: false

Constraints

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

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

Thinking Process

Subtract as You Go

Instead of accumulating a running sum and comparing at the leaf, subtract each node’s value from targetSum. At a leaf, check if the remainder is 0. This avoids carrying an extra parameter.

Three Cases

  1. Null node: return false (no path here)
  2. Leaf node (!left && !right): return whether remaining sum is 0
  3. Internal node: recurse on both children with reduced target

Why Check Leaf Explicitly?

A path must end at a leaf (node with no children). Without the leaf check, we might return true at an internal node where the sum happens to match but the path isn’t complete.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Approach: Top-Down DFS – O(n)

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        targetSum -= root->val;
        if (!root->left && !root->right) return targetSum == 0;
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: ### Subtract as You Go

How the code works:

  1. Null node: return false (no path here)
  2. Leaf node (!left && !right): return whether remaining sum is 0
  3. Internal node: recurse on both children with reduced target

Walkthrough — input root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22, expected output true:

Path 5 → 4 → 11 → 2 = 22

Alternative: Iterative (Stack) – O(n)

Use an explicit stack of (node, remaining) pairs. Same subtract-and-check logic, just without recursion.

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;

        stack<pair<TreeNode*, int>> stk;
        stk.push({root, targetSum - root->val});

        while (!stk.empty()) {
            auto [node, remaining] = stk.top();
            stk.pop();

            if (!node->left && !node->right && remaining == 0)
                return true;

            if (node->right) stk.push({node->right, remaining - node->right->val});
            if (node->left) stk.push({node->left, remaining - node->left->val});
        }

        return false;
    }
};

Time: O(n) Space: O(h) for the stack

Walk-Through: targetSum = 22

5  (remain: 22→17)
         / \
        4   8  (remain: 17→13)  (remain: 17→9)
       /      / \
      11     13  4  (remain: 13→2)
     / \
    7   2   ← leaf, remain: 2→0 ✓ return true

Common Mistakes

  • Returning true for root == null && targetSum == 0 – an empty tree has no path, answer is false
  • Not checking the leaf condition – returns true at internal nodes where the sum coincidentally matches
  • Using == check at every node instead of only at leaves

Key Takeaways

  • Subtract-and-check-at-leaf is cleaner than accumulate-and-compare
  • The explicit leaf check (!left && !right) is what distinguishes this from a general “does any partial path sum match” problem
  • This is the base pattern for LC 113 (collect all paths) and LC 437 (any-start path sum)

References

Template Reference