Path Sum in a Binary Tree: Remainders and Prefix Sums

"Path sum" is not one question but a family of three, and they are asked in sequence. Does a root-to-leaf path add up to the target? List every such path. Count the paths that add up to it when a path may start and end at any node, as long as it goes downwards. The tree is the same each time. What changes is what you carry down the recursion, and choosing that well is the whole skill.

The problem it solves

Take the lesson's tree: 5 at the root, with 4 on the left (and 11 below it) and 8 on the right (and 3 below it).

• Path sum I: is there a root-to-leaf path summing to 20? Yes, 5 + 4 + 11.
• Path sum II: return every root-to-leaf path that sums to the target, as lists of values.
• Path sum III: count downward paths anywhere in the tree summing to 11. There are two: the single node 11, and 8 + 3.

A brute force for the third question starts a walk from every node and follows every downward path, which is O(n²) on a degenerate tree. The goal is to share work between those walks.

The intuition

Version I: carry the remainder. Instead of a running total that you compare with the target at the end, subtract each node's value from the target on the way down. A leaf then only has to check for zero. It is the same arithmetic, but it means every call gets one number and answers one question: "does a path below me sum to this?"

The rule that trips people up is the leaf test. A remainder of zero halfway down is not an answer, because the question is about complete root-to-leaf paths. Only a node with no children may report a hit.

Version II: carry the path. Keep one list of the values from the root to the current node. Append on the way in, pop on the way out, and copy the list when a leaf hits zero. That is backtracking: a single shared list, restored after each child.

Version III: carry prefix sums. A downward path from node u to node v sums to the prefix sum at v minus the prefix sum just above u. So at each node, with current prefix cur, the number of paths ending here that sum to the target is the number of ancestors, or the empty prefix, whose prefix equals cur - target. Keep a hash map of prefix counts along the current root-to-node path, adding on the way in and removing on the way out. It is the tree version of subarray sum equals k, with the path from the root playing the role of the array.

The lesson's version of III keeps a list of every open path's running sum instead. It is simpler to reason about and costs O(h) per node for height h; the hash map cuts that to O(1).

Watch it run

The animation asks whether any root-to-leaf path adds up to 20 and carries the remainder down instead of a running total. At the root it subtracts 5, so both children are asked for 15, not for 20. At 4 it subtracts again, and the child is asked for 11. At leaf 11 there is nothing left to find: that path sums to 20. On the other branch, 8 leaves 7 for its child, and leaf 3 still needs 4. Too late: that path is over. One branch landed on zero and the other did not, and a remainder of zero halfway down would not have counted. Only at a leaf.

The code

The three versions on the lesson's tree:

from collections import defaultdict

class Node:
    def __init__(self, v, l=None, r=None):
        self.val, self.left, self.right = v, l, r

def has_path(n, target):                        # I: carry the remainder down
    if not n:
        return False
    rest = target - n.val
    if not n.left and not n.right:
        return rest == 0                        # only a leaf may say yes
    return has_path(n.left, rest) or has_path(n.right, rest)

def all_paths(root, target):                    # II: one shared list, backtracking
    out, path = [], []
    def walk(n, rest):
        if not n:
            return
        path.append(n.val)
        rest -= n.val
        if not n.left and not n.right and rest == 0:
            out.append(list(path))              # copy: the list keeps changing
        walk(n.left, rest)
        walk(n.right, rest)
        path.pop()                              # undo before returning
    walk(root, target)
    return out

def count_paths(root, target):                  # III: prefix sums in a hash map
    seen = defaultdict(int)
    seen[0] = 1                                 # the empty prefix above the root
    def walk(n, cur):
        if not n:
            return 0
        cur += n.val
        hits = seen[cur - target]               # paths ending here
        seen[cur] += 1
        hits += walk(n.left, cur) + walk(n.right, cur)
        seen[cur] -= 1                          # leave the path: forget this prefix
        return hits
    return walk(root, 0)

root = Node(5, Node(4, Node(11)), Node(8, Node(3)))
print(has_path(root, 20), has_path(root, 9))   # True False
print(all_paths(root, 20), all_paths(root, 16))   # [[5, 4, 11]] [[5, 8, 3]]
print(count_paths(root, 11))                    # 2

The remainder each node is asked for, in the order the animation visits them:

def remainders(n, target, log):
    if n:
        log.append((n.val, target - n.val))
        remainders(n.left, target - n.val, log)
        remainders(n.right, target - n.val, log)
    return log

print(remainders(root, 20, []))
# [(5, 15), (4, 11), (11, 0), (8, 7), (3, 4)]

All three against brute force on 2,000 random trees with negative values allowed, where the brute force lists every root-to-leaf path and every downward path explicitly:

import random

def random_tree(n):
    if n == 0:
        return None
    k = random.randint(0, n - 1)
    return Node(random.randint(-3, 5), random_tree(k), random_tree(n - 1 - k))

def root_to_leaf(n):
    if not n:
        return []
    if not n.left and not n.right:
        return [[n.val]]
    return [[n.val] + p for p in root_to_leaf(n.left) + root_to_leaf(n.right)]

def downward_sums(n):                           # every path starting at n, going down
    if not n:
        return []
    return [n.val] + [n.val + s for s in downward_sums(n.left) + downward_sums(n.right)]

def all_nodes(n):
    return [n] + all_nodes(n.left) + all_nodes(n.right) if n else []

random.seed(20)
ok = True
for _ in range(2000):
    t = random_tree(random.randint(0, 12))
    target = random.randint(-3, 10)
    full = [p for p in root_to_leaf(t) if sum(p) == target]
    ok &= has_path(t, target) == bool(full)
    ok &= all_paths(t, target) == full
    ok &= count_paths(t, target) == sum(downward_sums(u).count(target) for u in all_nodes(t))
print(ok)                                       # True

The complexity

• Version I: O(n) time, each node visited at most once, and O(h) stack space for tree height h.
• Version II: O(n) visits, plus the cost of copying hits. In the worst case that is O(n · h) output, because a copy is as long as the path.
• Version III with a hash map: O(n) time and O(h) extra space for the map and the stack.
• Version III with a list of open sums, as in the lesson: O(n · h) time, which is O(n log n) on a balanced tree and O(n²) on a chain.

Where it goes wrong

• Accepting a zero remainder at an inner node. Test for a leaf first; has_path(root, 9) is false even though 5 + 4 = 9.
• Treating an empty tree as a zero-sum path. With no root there is no path, so the answer is false, even for a target of 0.
• Appending the shared list itself in version II. Every stored "path" then points at the same list, which ends empty. Copy it.
• Forgetting to undo in version III. If the prefix count is not decremented on the way out, a sibling subtree sees prefixes from a branch it is not on.
• Stopping early with negative values. Values can be negative, so exceeding the target does not mean the path is dead.

When it shows up in interviews

The three versions are a common ladder in tree rounds: I checks recursion, II checks backtracking, and III checks whether you spot the prefix-sum trick from arrays. Expect a question about why the leaf test matters and about the complexity on a skewed tree. The same "what do I pass down, what do I return up?" choice drives diameter of a binary tree and validate a BST.

How to say it in an interview

"For the root-to-leaf version I carry the remainder: subtract each node's value on the way down, and only a leaf reports a hit when the remainder is zero. That is linear time and height-sized stack. To list the paths I keep one path list, append on entry, pop on exit, and copy it at a matching leaf. For paths that can start anywhere, a downward path is a difference of two prefix sums on the same root-to-node path, so I keep a hash map of prefix counts along the current path. At each node I add the count of cur - target, recurse, then decrement my prefix on the way out. That is O(n) instead of O(n · h)."