Path Sum

Difficulty: Easy

Problem

You are given the root of a binary tree and an integer targetSum. Return true if some path that starts at the ROOT and finishes at a LEAF (a node with no children) has node values adding up to exactly targetSum, otherwise return false. Stopping at a node that still has children does not count.

Example

Input: root = [7,3,9,1,4,null,2], targetSum = 14
Output: true
Explanation: The path 7 → 3 → 4 adds up to 7 + 3 + 4 = 14, and node 4 is a leaf. The other two root-to-leaf paths total 11 and 18.

Brute-force approach

There is no meaningful brute force vs optimal split. The recursive remaining-sum walk IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: Think 'how much is LEFT?' instead of 'how much so far?'. One shrinking number rides down the recursion, and leaves give an instant yes/no.

Walk down the tree carrying the amount still needed. Each node subtracts its own value; a leaf succeeds if exactly 0 remains.

Steps

  1. Base case: null has no paths, return false
  2. Compute remaining = targetSum − node.val
  3. If the node is a leaf, return remaining == 0
  4. Otherwise ask both children with the new remaining, combined with OR

Time complexity: O(n) · Space complexity: O(h) where h = height of tree

Pseudocode

function hasPathSum(root, targetSum):
    if root is null:
        return ____
    
    remaining = targetSum - ____
    
    if root.left is null and root.right is null:
        return remaining == ____
    
    return hasPathSum(root.left, remaining) ____ \
           hasPathSum(root.right, remaining)

Hints

  • Base case: can an empty spot ever complete a path? (No: what boolean is that?)
  • Each node pays its share: subtract the node's own value from the target
  • At a leaf, success means NOTHING is left to pay, compare remaining with what?
  • One successful child is enough. Which boolean operator combines the two calls?

Complexity questions

What is the worst-case time complexity, and when can it finish early?

O(n) worst case; a success in the first explored subtree short-circuits the rest. If no path matches, every node is visited once → O(n). But the OR short-circuits: the first successful leaf stops all further exploration.

What is the space complexity of this recursion?

O(h): one small stack frame per level, each holding a single number. Each frame stores just 'remaining', one number. The stack grows to the tree's height: O(log n) balanced, O(n) skewed. No path lists are ever stored.

Why does carrying 'remaining' avoid the cleanup that carrying a path list would need?

Numbers are passed by value: every call owns its copy, so failed branches need no undo. A shared path list must be pushed/popped around every recursion (backtracking). A plain number is copied into each call. When a branch fails, its number simply disappears with the frame.

To also RETURN the winning path (not just true/false), what would change?

Carry a path list down and backtrack (or rebuild via parent pointers), about O(h) extra space. You'd carry a growing list (push before recursing, pop after: classic backtracking) or record parents and rebuild. Either way about O(h) extra space for the path itself.

Check your understanding of Path Sum

What counts as a valid path in this problem?

A path from the root all the way down to a LEAF. The path must start at the root AND end at a leaf (a node with no children). Stopping midway at an internal node doesn't count: even if the sum matches there.

root = [1,2,3] with targetSum = 5. True or false?

False: the only root-to-leaf paths are 1→2 (sum 3) and 1→3 (sum 4). Paths always start at the root, so 2+3 is not a path. The two real paths are 1→2 = 3 and 1→3 = 4. Neither equals 5 → false.

The subtraction trick: we arrive at a node with value v while needing k. What do we pass down to the children?

k − v: whatever is still needed after this node pays its share. Each node 'pays' its own value and passes down the REMAINING need: k − v. Carrying 'what's still needed' means every call handles just one small number: no path lists, no global state.

Where exactly do we check for success?

At a LEAF: remaining must be exactly 0 after the leaf pays its value. The check happens ONLY at leaves: after subtracting the leaf's value, remaining must equal 0. Checking at null instead is the classic bug. A node with one child would get a phantom 'path' through its missing child.

root = [] (empty tree) with targetSum = 0. True or false?

False: an empty tree has no root-to-leaf paths at all. A path needs at least a root and a leaf. An empty tree has neither, so there is no path, not even one summing to 0. Return false.

Related problems

Keep practising