DSA

Path Sum

Check if a root-to-leaf path sums to a target. Optimal — Time O(n), Space O(h).

September 12, 2026
PatternTree DFS (Recursion)OptimalO(n) time · O(h) space
Solve on LeetCode
Key insighttry it first, then reveal

At each node, subtract the node's value from the remaining target and recurse into the children.

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#

cpp
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.