DSA Path Sum

The problem

A root-to-leaf path is a chain of nodes from the root down to a leaf. A leaf is a node with no children. The question gives a tree and a target number, and asks whether the values on any one root-to-leaf path add up to that target.

A path must end at a leaf. A chain that stops early never counts, even when its running total hits the target. The code below prints one tree in level order, lists every root-to-leaf sum, and states the verdicts the article will use.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def path_sums(node, running, found):
    if node is None:
        return
    running += node.value
    if node.left is None and node.right is None:
        found.append(running)
        return
    path_sums(node.left, running, found)
    path_sums(node.right, running, found)

tree_a = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8, TreeNode(13), TreeNode(4)))
tree_b = TreeNode(1, TreeNode(2), TreeNode(3))
sums = []
path_sums(tree_a, 0, sums)
print("tree A level order:", level_order(tree_a))
print("tree A path sums:", sums)
print("tree A reaches 22: expected True")
print("tree A reaches 9: expected False")
print("tree B path sums need 22: expected False")
print("single node 22 reaches 22: expected True")

Tree A has four root-to-leaf paths. One of them is 5 + 4 + 11 + 2, which is 22. No path in tree A sums to 9, even though 5 + 4 does. Node 4 is not a leaf, so that chain is unfinished.

Intuition

The first idea follows one chain and watches its running total. The total hits the target, so the chain looks like an answer. The trap is where the chain stops.

In tree A, the chain 5 then 4 totals 9 after two steps. Node 4 still has a child, so the chain has not reached a leaf. A check that celebrates early reports a path that does not exist.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def early_stop(node, target, running=0):
    if node is None:
        return False
    running += node.value
    if running == target:
        return True
    return early_stop(node.left, target, running) or early_stop(node.right, target, running)

def proper(node, target):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return target == node.value
    target -= node.value
    return proper(node.left, target) or proper(node.right, target)

tree = TreeNode(5, TreeNode(4, TreeNode(11)), TreeNode(8))
print("early-stop check, target 9:", early_stop(tree, 9))
print("leaf-only check, target 9:", proper(tree, 9))
print("leaf-only check, target 20:", proper(tree, 20))

The two checks disagree on target 9 and agree on target 20. The path 5 + 4 + 11 is a real root-to-leaf path, so 20 is a genuine answer. The leaf test is what separates the two.

Brute force

The straightforward route lists everything. Walk every root-to-leaf path, add up each one in full, and store each sum. Then answer by looking the target up in the list.

The route is correct and easy to trust. Its cost is the full walk plus the stored list. It also walks every path even when the first path already hits the target.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

visits = 0

def collect(node, running, found):
    global visits
    if node is None:
        return
    visits += 1
    running += node.value
    if node.left is None and node.right is None:
        found.append(running)
        return
    collect(node.left, running, found)
    collect(node.right, running, found)

tree_a = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8, TreeNode(13), TreeNode(4)))
found = []
visits = 0
collect(tree_a, 0, found)
print("path sums:", found)
print("target 22 in list:", 22 in found)
print("nodes visited:", visits)
print("sums stored:", len(found))

The list holds four sums for a nine-node tree. A bigger tree stores one sum per leaf. The optimal search stores no list and can stop at the first success.

The optimal solution: shrink the target on the way down

The key idea is one sentence. Carry the target down the tree, subtract each node's value from it, and let a leaf answer yes exactly when the remaining target equals its own value.

One successful path is enough. The or in the return line stops the search as soon as one side answers yes. No sums are stored.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def has_path(node, target):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return target == node.value
    target -= node.value
    return has_path(node.left, target) or has_path(node.right, target)

tree_a = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8, TreeNode(13), TreeNode(4)))
tree_b = TreeNode(1, TreeNode(2), TreeNode(3))
print("tree A reaches 22:", has_path(tree_a, 22))
print("tree A reaches 9:", has_path(tree_a, 9))
print("tree B reaches 22:", has_path(tree_b, 22))
print("single node 22 reaches 22:", has_path(TreeNode(22), 22))
print("empty tree reaches 0:", has_path(None, 0))

Every case from the first section matches its expected verdict. The empty tree answers False even for target 0. No path exists in an empty tree, so no sum can count.

Walkthrough

Follow target 22 down the left side of a small tree. The tree has root 5, a left child 4 with a left child 11, and a right child 8. The trace prints the remaining target at each node.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def traced(node, target, depth=0):
    if node is None:
        return False
    print("  " * depth + "node", node.value, "remaining target:", target)
    if node.left is None and node.right is None:
        print("  " * depth + "leaf: match" if target == node.value else "  " * depth + "leaf: no match")
        return target == node.value
    rest = target - node.value
    return traced(node.left, rest, depth + 1) or traced(node.right, rest, depth + 1)

tree = TreeNode(5, TreeNode(4, TreeNode(11)), TreeNode(8))
print("verdict:", traced(tree, 22))

At the root, 22 is still whole. Below 5 the remainder is 17, and below 4 it is 13. The leaf 11 does not equal 13, so that path fails and the search tries the right child. The leaf 8 also misses its remainder, which is 17, so this small tree answers False. In tree A the same walk reaches the leaf 2 with remainder 2, and that exact match is the success.

Complexity

Time is O(n) in the worst case for a tree of n nodes. A failed search visits every node, and a successful search may still visit most of them before it finds its path.

Space is O(h) for a tree of height h. The memory is the call stack along one path. The brute force also pays O(number of leaves) to store its list of sums.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

visits = 0

def collect(node, running, found):
    global visits
    if node is None:
        return
    visits += 1
    running += node.value
    if node.left is None and node.right is None:
        found.append(running)
        return
    collect(node.left, running, found)
    collect(node.right, running, found)

def has_path(node, target):
    global visits
    if node is None:
        return False
    visits += 1
    if node.left is None and node.right is None:
        return target == node.value
    target -= node.value
    return has_path(node.left, target) or has_path(node.right, target)

def build(depth):
    if depth == 0:
        return None
    return TreeNode(1, build(depth - 1), build(depth - 1))

for depth in [3, 4, 5]:
    tree = build(depth)
    found = []
    visits = 0
    collect(tree, 0, found)
    brute = visits
    visits = 0
    has_path(tree, 999)
    print("depth", depth, "brute visits:", brute, "failed-search visits:", visits, "paths:", len(found))

On a failed target both routes visit every node, so the counts match. The saving is elsewhere. The optimal search stores nothing and stops early on a success, while the list route always walks and stores everything.

Edge cases and pitfalls

A single node is both root and leaf. Its value alone is a complete path, so it matches only its own value as target. An empty tree has no path at all and answers False for every target.

Negative values break a common shortcut. A running total can pass the target and come back later, so the search must never prune a path just because its partial sum overshot. The leaf equality test handles negatives with no special case.

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

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def has_path(node, target):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return target == node.value
    target -= node.value
    return has_path(node.left, target) or has_path(node.right, target)

neg = TreeNode(5, TreeNode(-3), TreeNode(2))
print("empty, target 0:", has_path(None, 0))
print("single 7, target 7:", has_path(TreeNode(7), 7))
print("single 7, target 8:", has_path(TreeNode(7), 8))
print("path 5 + -3 = 2:", has_path(neg, 2))
print("root alone is not a path here:", has_path(neg, 5))

The last two lines carry the lesson. The sum 2 counts because its chain ends at the leaf -3. The sum 5 does not count, because the root of that tree is not a leaf.