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. Try targetSum = 16 as well: 7 + 9 = 16 reaches node 9 with nothing left to pay, but 9 still has a child (2), so it is not a leaf and the answer is false. The animation walks this case.

Brute-force approach

The first idea is the collector's version: list every root-to-leaf path, add up each one, and ask whether the target is among the sums. On the statement example [7,3,9,1,4,null,2] there are 3 paths ([7,3,1], [7,3,4], [7,9,2]), 9 values copied into the lists and 6 additions (sums 11, 14, 18). It is correct but blind: it cannot stop early, and the stored paths are overhead for a yes/no question. The video derives the subtraction (carry what is still needed) from this list.

Steps

  1. Walk the tree and write down every root-to-leaf path
  2. Add up the values of each path
  3. Return true if any sum equals targetSum

Time complexity: O(n) time, but it always visits every node · Space complexity: O(n) for the stored paths (n values per path in the worst case)

Trade-offs

  • Copies every path: 9 values and 6 additions for 3 short paths on the example
  • Cannot stop at the first success

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?
  • A node's totals from here are its value plus one sum from a child, so asking whether T is among them is asking whether T minus the value is among a child's. That is why you subtract and pass the rest down.
  • Zero left at a node that has children proves nothing: a path must end at a leaf, so only test remaining == 0 at a leaf.

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