Path Sum Problems: All Variants Explained

Path sum problems are among the most popular tree interview questions. They start simple (does a path exist?) and progressively get harder (count all paths from any node to any descendant). The key progression is:

• Path Sum I: Yes/no question, root-to-leaf
• Path Sum II: Collect all paths, root-to-leaf
• Path Sum III: Count paths, any-to-any descendant (prefix sum technique)

Mastering this progression covers a huge range of tree + DFS patterns.

TreeNode definition

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Path Sum I — does a path exist?

LeetCode 112: Given the root and a target sum, return True if there exists a root-to-leaf path where the sum of node values equals the target.

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

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

Solution: subtract as you go

Instead of tracking the running sum, subtract the current node’s value from the target. When you reach a leaf, check if the remaining target is 0.

def hasPathSum(root, targetSum):
    """
    Path Sum I: does a root-to-leaf path sum to target?
    Time: O(n)  Space: O(h) recursion stack
    """
    if not root:
        return False

    # Subtract current value
    targetSum -= root.val

    # Leaf check
    if not root.left and not root.right:
        return targetSum == 0

    return (hasPathSum(root.left, targetSum) or
            hasPathSum(root.right, targetSum))

Why subtract instead of accumulate?

Both work, but subtraction is cleaner — you avoid passing an extra current_sum parameter. The check becomes remaining == 0 instead of current_sum == target.

Iterative version with stack

def hasPathSum(root, targetSum):
    """Iterative DFS with stack."""
    if not root:
        return False

    stack = [(root, targetSum - root.val)]

    while stack:
        node, remaining = stack.pop()

        # Leaf with sum matched
        if not node.left and not node.right and remaining == 0:
            return True

        if node.right:
            stack.append((node.right, remaining - node.right.val))
        if node.left:
            stack.append((node.left, remaining - node.left.val))

    return False

Common mistake: forgetting the leaf check

A node with one child is not a leaf. If you check if node is None and remaining == 0, you will incorrectly match non-leaf paths:

# WRONG — treats null children as valid endpoints
def hasPathSum_wrong(root, target):
    if not root:
        return target == 0  # Bug: null is not a leaf
    return (hasPathSum_wrong(root.left, target - root.val) or
            hasPathSum_wrong(root.right, target - root.val))

The correct approach explicitly checks not root.left and not root.right.

Path Sum II — find all paths

LeetCode 113: Return all root-to-leaf paths where the sum equals the target.

def pathSum(root, targetSum):
    """
    Path Sum II: find all root-to-leaf paths that sum to target.
    Time: O(n * h) — n nodes, each path up to h long
    Space: O(h) recursion + O(n * h) for result
    """
    result = []

    def dfs(node, remaining, path):
        if not node:
            return

        path.append(node.val)

        # Leaf with sum matched
        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])  # Copy the path

        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)

        path.pop()  # Backtrack

    dfs(root, targetSum, [])
    return result

Backtracking explained

The path.pop() after recursive calls is the backtracking step. We reuse a single path list and undo each addition as we return up the tree. This is more memory-efficient than creating a new list at each recursive call.

Without backtracking (creates new lists):

def pathSum_no_backtrack(root, targetSum):
    """Less efficient — creates new list at each call."""
    result = []

    def dfs(node, remaining, path):
        if not node:
            return
        new_path = path + [node.val]  # New list each time
        if not node.left and not node.right and remaining == node.val:
            result.append(new_path)
        dfs(node.left, remaining - node.val, new_path)
        dfs(node.right, remaining - node.val, new_path)

    dfs(root, targetSum, [])
    return result

The backtracking version uses O(h) space for the path, while this version uses O(h) at each level, totaling O(h^2) in the worst case.

Why path[:] instead of path?

path is a mutable list that changes as we traverse. If we append path directly to result, we store a reference to the same list. By the time the function ends, that list will be empty (all elements popped). path[:] creates a snapshot copy.

Path Sum III — any-to-any (prefix sum)

LeetCode 437: Count paths from any node to any descendant where the sum equals the target. The path does not need to start at root or end at a leaf.

This is a significant jump in difficulty. The key insight: this is the tree version of “subarray sum equals K” — and the solution uses the same prefix sum + hashmap technique.

Brute force: O(n^2)

For each node, try starting a path from it and count valid paths going downward:

def pathSum3_brute(root, targetSum):
    """
    Brute force: try every node as path start.
    Time: O(n^2) in worst case (skewed tree)
    Space: O(h) recursion
    """
    if not root:
        return 0

    def countFrom(node, remaining):
        """Count paths starting from this node going down."""
        if not node:
            return 0
        count = 1 if node.val == remaining else 0
        count += countFrom(node.left, remaining - node.val)
        count += countFrom(node.right, remaining - node.val)
        return count

    # Try every node as starting point
    return (countFrom(root, targetSum) +
            pathSum3_brute(root.left, targetSum) +
            pathSum3_brute(root.right, targetSum))

Optimal: prefix sum O(n)

The prefix sum approach tracks the cumulative sum from root to the current node. If current_sum - target has been seen before, then the subpath from that earlier point to now sums to target.

from collections import defaultdict

def pathSum3(root, targetSum):
    """
    Prefix sum approach — O(n) time.
    Same technique as 'subarray sum equals K'.
    Time: O(n)  Space: O(h) for recursion + hashmap
    """
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1  # Empty prefix (path starting from root)

    def dfs(node, current_sum):
        if not node:
            return 0

        current_sum += node.val
        # How many times have we seen (current_sum - target)?
        count = prefix_counts[current_sum - targetSum]

        # Record this prefix sum
        prefix_counts[current_sum] += 1

        # Continue to children
        count += dfs(node.left, current_sum)
        count += dfs(node.right, current_sum)

        # Backtrack — remove this prefix when leaving the subtree
        prefix_counts[current_sum] -= 1

        return count

    return dfs(root, 0)

Why backtrack the prefix map?

The prefix sum technique works for arrays because subarrays are contiguous. In trees, when we move to a sibling subtree, the path from root changes. We must remove the current node’s prefix from the map to avoid counting paths that jump across branches.

         1
        / \
       2   3

At node 2: prefix_counts = {0:1, 1:1, 3:1}
After leaving node 2: remove 3 → {0:1, 1:1}
At node 3: prefix_counts = {0:1, 1:1, 4:1}  ← correct, 3 not counted

Step-by-step example

Tree:     10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1

Target = 8

Valid paths:

1. 5 → 3 = 8
2. 5 → 2 → 1 = 8
3. -3 → 11 = 8
4. 10 → 5 → 3 → -2 = (wrong, that’s 16)

Wait, let me recalculate: 10 → -3 → 11 is not a path (not root-to-descendant in a line). Actually, -3 → 11 = 8 is valid. And 10 → 5 → 3 is not 8, but 5 → 3 = 8 is valid.

Answer: 3 paths.

Maximum path sum (any-to-any)

LeetCode 124: Find the maximum sum of any path in the tree. The path can start and end at any node (not necessarily root or leaf).

def maxPathSum(root):
    """
    Maximum path sum — any node to any node.
    Time: O(n)  Space: O(h)
    """
    max_sum = float('-inf')

    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0

        # Max sum from left/right subtrees (ignore negative branches)
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)

        # Path through this node connecting left and right
        path_through = node.val + left_gain + right_gain
        max_sum = max(max_sum, path_through)

        # Return max gain if we continue upward (can only go one direction)
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return max_sum

Key insight: return vs update

At each node, we make two different calculations:

1. Update global max: Consider the path that goes left → node → right (using both branches). This might be the answer but cannot be extended upward.

2. Return to parent: The parent can only use one branch. Return node.val + max(left, right) so the parent can extend the path.

The max(..., 0) ensures we never take a negative branch — it is better to not include a subtree than to include one with negative sum.

Sum root-to-leaf numbers

LeetCode 129: Each root-to-leaf path forms a number (e.g., path 1→2→3 = 123). Return the sum of all such numbers.

def sumNumbers(root):
    """
    Sum of all root-to-leaf numbers.
    Time: O(n)  Space: O(h)
    """
    def dfs(node, current_num):
        if not node:
            return 0

        current_num = current_num * 10 + node.val

        # Leaf — return the formed number
        if not node.left and not node.right:
            return current_num

        return dfs(node.left, current_num) + dfs(node.right, current_num)

    return dfs(root, 0)

Complexity comparison

Problem	Time	Space	Technique
Path Sum I	O(n)	O(h)	DFS + subtraction
Path Sum II	O(n*h)	O(h) + result	DFS + backtracking
Path Sum III (brute)	O(n^2)	O(h)	DFS from every node
Path Sum III (optimal)	O(n)	O(h)	Prefix sum + hashmap
Max Path Sum	O(n)	O(h)	Post-order DFS
Sum Root-to-Leaf	O(n)	O(h)	Pre-order DFS

Pattern recognition

All path sum problems share a DFS skeleton. The differences are:

1. What do you track? Running sum, prefix map, or formed number
2. Where do you check? At leaves only, or at every node
3. What do you return? Boolean, count, list of paths, or max value
4. Do you backtrack? Yes for Path Sum II and III, no for I

# Generic path DFS skeleton
def pathDFS(node, state):
    if not node:
        return BASE_CASE

    # Update state with current node
    update(state, node)

    # Check condition (at leaf? at every node?)
    if condition(node, state):
        record_result()

    # Recurse
    pathDFS(node.left, state)
    pathDFS(node.right, state)

    # Backtrack if needed
    undo(state, node)

Edge cases

def test_edge_cases():
    # Single node equals target
    root = TreeNode(5)
    assert hasPathSum(root, 5) == True
    assert hasPathSum(root, 3) == False

    # Negative values
    root = TreeNode(-2, None, TreeNode(-3))
    assert hasPathSum(root, -5) == True

    # All zeros
    root = TreeNode(0, TreeNode(0), TreeNode(0))
    assert pathSum3(root, 0) == 4  # Many zero-sum paths

    # Single negative node
    root = TreeNode(-3)
    assert maxPathSum(root) == -3  # Must include at least one node

Practice problems

Problem	Difficulty	Link
Path Sum	Easy	LeetCode 112
Path Sum II	Medium	LeetCode 113
Path Sum III	Medium	LeetCode 437
Binary Tree Maximum Path Sum	Hard	LeetCode 124
Sum Root to Leaf Numbers	Medium	LeetCode 129
Longest Univalue Path	Medium	LeetCode 687
Diameter of Binary Tree	Easy	LeetCode 543

Key takeaways

1. Path Sum I/II are root-to-leaf DFS — check only at leaf nodes
2. Path Sum III is the “subarray sum = K” technique applied to trees — use prefix sums with backtracking
3. Maximum path sum uses post-order DFS — return single-branch gain, update global with both-branch path
4. Always backtrack mutable state (path list, prefix map) when leaving a subtree
5. The max(gain, 0) trick lets you ignore negative subtrees cleanly