Path Sum

Practice Link

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

This is the simpler precursor to Path Sum II, which asks for all such paths instead of just a yes/no answer.

Examples#

Example 1

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

        5
       / \
      4   8
     /   / \
    11  13   4
   /  \       \
  7    2       1

Path: 5 → 4 → 11 → 2  =  22 ✓

Example 2

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

Paths: 1→2 (sum=3), 1→3 (sum=4). Neither equals 5.

Example 3

Input: root = [], targetSum = 0
Output: false  — empty tree has no root-to-leaf paths.

Intuition#

At each node, subtract the node's value from the remaining target and recurse into the children. The problem reduces to: "Does the left or right subtree have a path summing to targetSum - node->val?"

The base cases handle the two terminating conditions:

• root == null — walked off the tree without hitting a leaf → return false.
• root->val == targetSum and the node is a leaf (no children) — found the exact path → return true. The leaf check is critical: without it, val == remaining at an internal node would give a false positive when children still add to the sum.

The recursive OR means we stop as soon as either branch finds a valid path (short-circuit evaluation), so we never explore more of the tree than needed.

Solution#

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

        // Leaf node: check if remaining target is consumed exactly
        if (root->val == targetSum && !root->left && !root->right)
            return true;

        return hasPathSum(root->left,  targetSum - root->val)
            || hasPathSum(root->right, targetSum - root->val);
    }
};

Time Complexity: O(n) — each node is visited exactly once.
Space Complexity: O(h) — recursion stack depth equals tree height; O(log n) for a balanced tree, O(n) worst-case for a skewed tree.

Why subtract, not accumulate?#

An alternative passes a running sum down and checks runningSum == targetSum at the leaf. Both work, but subtracting is slightly cleaner: the leaf condition root->val == remaining is self-contained and doesn't need to know the original targetSum at the leaf level.

Follow-up#

Consider: Can you solve this iteratively?

Yes — use an explicit stack that stores {node, remainingSum} pairs (DFS). Pop a pair, check the leaf condition, and push non-null children with remainingSum - child->val. This avoids the call-stack overhead and runs in the same O(n) / O(h) bounds.

Path Sum II (LeetCode 113) extends this to return all root-to-leaf paths with the target sum — solved with DFS + backtracking. Path Sum III (LeetCode 437) allows paths to start and end at any node, not just root-to-leaf.