Path Sum & Root-to-Leaf Techniques

The previous pattern was about visiting nodes. This one is about the journeys between them, specifically the paths that run from the root all the way down to a leaf. A root-to-leaf path is a full story: a chain of decisions, a sequence of values, a complete route from where you started to where the tree ends. Many real questions are not about individual nodes at all but about these whole paths: does any path add up to a target, which path is heaviest, what does each path spell out, how many paths satisfy some rule. The skill is descending the tree while carrying the story of the path so far, and acting on it the moment you hit a leaf.

The mechanism is depth-first traversal with one addition: state that travels down with you. As you step onto a node you extend the path (add its value to a running sum, push it onto the current route), you recurse into the children carrying that extended state, and here is the heartbeat, on the way back up you undo the extension so the sibling branch starts from a clean slate. Add on the way down, remove on the way back up. That push-then-pop is the exact same choose-explore-un-choose discipline as backtracking, which is no coincidence: root-to-leaf work is backtracking on a tree.

Carry the path down, act at the leaf, undo on the way back

Finding every root-to-leaf path that sums to a target shows all three moves at once: extend, check-at-leaf, undo.

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

def path_sum(root, target):
    result = []
    def dfs(node, path, running):
        if not node:
            return
        path.append(node.val)                       # extend on the way down
        running += node.val
        if not node.left and not node.right:        # a leaf: the path is complete
            if running == target:
                result.append(path[:])              # copy, the path keeps mutating
        else:
            dfs(node.left,  path, running)          # explore, carrying the state
            dfs(node.right, path, running)
        path.pop()                                  # undo before the caller tries a sibling
    dfs(root, [], 0)
    return result

root = TreeNode(5,
                TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
                TreeNode(8, TreeNode(13), TreeNode(4, TreeNode(5), TreeNode(1))))
print(path_sum(root, 22))                           # [[5, 4, 11, 2], [5, 8, 4, 5]]

Two details carry the whole pattern. The path[:] copy when recording a hit, because path is one list mutated throughout the search, so storing it directly would save a reference that later gets emptied. And the path.pop() at the end of every call, which is the undo: without it, the values from one branch leak into the next and every path after the first is wrong. Notice too that we only test at a leaf (not node.left and not node.right), because a root-to-leaf path is only complete when there is nowhere left to go.

A binary tree rooted at 5 with the two root-to-leaf paths that sum to 22 highlighted, 5-4-11-2 and 5-8-4-5; depth-first search carries a running total down each path and records it at the leaf, undoing the last step on the way back up.

In the wild: turning a decision tree into readable rules

Train a decision tree classifier (for loan approval, spam detection, medical triage) and you get an opaque tree of "if feature X is below this threshold go left, otherwise go right," with a prediction at each leaf. To explain the model to a human or an auditor, you extract its rules, and every rule is exactly one root-to-leaf path: the conditions you accumulate on the way down, joined together, imply the leaf's prediction.

def extract_rules(node, conditions, rules):
    if node.is_leaf:
        rules.append((list(conditions), node.prediction))   # the path IS the rule
        return
    conditions.append(f"{node.feature} <= {node.threshold}")
    extract_rules(node.left, conditions, rules)             # left = condition true
    conditions.pop()                                        # undo before the right branch

    conditions.append(f"{node.feature} > {node.threshold}")
    extract_rules(node.right, conditions, rules)            # right = condition false
    conditions.pop()                                        # undo on the way back up

Structurally this is the same function as path_sum. The accumulator changed from a running integer to a growing list of conditions, and the leaf action changed from "check the sum" to "emit a rule," but the skeleton is identical: extend the state descending, act at the leaf, undo ascending. That is why it belongs to the same pattern, and the accumulator can be anything the problem needs, a sum, a product of probabilities down a game tree, the digits a path spells into a number, the breadcrumb trail to a page. Recognize the "accumulate down, decide at the leaf, undo on the way up" shape and a whole category of tree problems collapses into this one template.

The trigger

The question is about entire root-to-leaf paths, not single nodes: paths that hit a target sum, the maximum-value path, all paths matching a rule, or what each path encodes. The tell is needing information that accumulates as you descend, so you find yourself wanting to carry a running total or a running list down the tree. That carried-and-undone state is the pattern.

Where it shows up

  • Path conditions: root-to-leaf paths summing to a target, paths spelling a number, longest or maximum-sum path.
  • Rule and trail extraction: reading a decision tree as if-then rules, building breadcrumb trails, tracing a chain of command.
  • Constrained enumeration: collecting all paths that satisfy a predicate, often with early pruning when a partial path already fails.

Where it bites

The signature bug is the missing undo, the forgotten pop, which lets one branch's state bleed into its siblings and silently corrupts every later path. Close behind is saving the mutable path by reference instead of copying, so all your stored results end up pointing at the same emptied list. Watch the leaf test too: checking the target at internal nodes instead of only at leaves answers a different (path-prefix) question. And because the number of root-to-leaf paths can be exponential in a bushy tree, collecting them all can blow up memory even when the traversal itself is fine.

When it is the wrong tool

If you only need a yes/no ("does any path sum to the target") rather than every path, do not collect them all, return True as soon as one qualifies and prune the rest. If the interesting path can start and end anywhere, not just root to leaf (a maximum path between two arbitrary nodes), this template is too narrow and you want a postorder computation that combines the best downward paths at each node. And if the same subtree is being re-explored under different accumulated states with heavy overlap, plain recursion recomputes it, and memoization (tree dynamic programming) is the honest fix.

Its neighbors

This pattern sits right between Binary Tree Traversals, which it extends by carrying state down the descent, and Backtracking, whose choose-explore-un-choose it reproduces exactly on a tree. When paths overlap and get recomputed, it grows into tree Dynamic Programming. And the yes/no and maximum-path variants lean on the same DFS spine, just changing what happens when a path completes.

References