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

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.

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);
    }
};

Time: $O(n)$ – visit each node at most once Space: $O(h)$ recursion stack ($O(\log n)$ balanced, $O(n)$ skewed)

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)

Template Reference