Module 17 · Binary Trees: Recursive DFS and Structural Contracts

170. Root-to-Leaf Target Sum

Interview · Download this solution · All solutions and shared helpers

Problem

Return whether a binary tree contains a root-to-leaf path whose integer values sum to target. A leaf has neither child. Negative and zero values are allowed. An empty tree has no such path, even when target is zero. Leave the tree unchanged.

Examples

Example 1

has_path_sum(build_tree([5,2,9]),7)
=> True

The left leaf completes a sum of seven.

Example 2

has_path_sum(build_tree([5,2]),5)
=> False

Stopping at the internal root is forbidden.

Example 3

has_path_sum(None,0)
=> False

An empty tree supplies no root-to-leaf path.

Example 4

has_path_sum(build_tree([3,-5]),-2)
=> True

Negative values are handled by subtraction without pruning.

Reveal the worked solution and reasoning

Why this mechanism works

Pass the unfinished obligation down the tree: after visiting a node, subtract its value from remaining. Reaching zero at an internal node is insufficient because the requested path must end at a leaf. Negative values also make remaining<0 an invalid pruning rule.

State and boundaries

has_path_sum(node,remaining) asks whether a path starting at node and ending at a leaf contributes exactly remaining.

Protocol

Reject an absent node.
Subtract the current value.
At a leaf test whether the remainder is zero.
Otherwise ask either child to fulfill the new remainder.

Visualization

target 7
root 5 -> remainder 2
child 2 is a leaf -> remainder 0 -> success
an internal sum of 7 alone would not suffice

Python implementation

from structures import build_tree

def has_path_sum(root, target):
    if root is None:
        return False
    remaining = target - root.val
    if root.left is None and root.right is None:
        return remaining == 0
    return (has_path_sum(root.left, remaining)
            or has_path_sum(root.right, remaining))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

has_path_sum(build_tree([5,2,9]),7)

L4 has_path_sum: if root is None:
root=N1(val=5,left=N2,right=N3); target=7

L6 has_path_sum: remaining = target - root.val
root=N1(val=5,left=N2,right=N3); target=7; remaining=2

L4 has_path_sum: if root is None:
root=N2(val=2,left=None,right=None); target=2

L6 has_path_sum: remaining = target - root.val
root=N2(val=2,left=None,right=None); target=2; remaining=0

Result: True. The left leaf completes a sum of seven.

has_path_sum(build_tree([5,2]),5)

L4 has_path_sum: if root is None:
root=N1(val=5,left=N2,right=None); target=5

L6 has_path_sum: remaining = target - root.val
root=N1(val=5,left=N2,right=None); target=5; remaining=0

L4 has_path_sum: if root is None:
root=N2(val=2,left=None,right=None); target=0

L6 has_path_sum: remaining = target - root.val
root=N2(val=2,left=None,right=None); target=0; remaining=-2

L4 has_path_sum: if root is None:
root=None; target=0

Result: False. Stopping at the internal root is forbidden.

Why the solution is correct

At a leaf the only candidate path consists of that node, so the subtraction test is exact. At an internal node every valid path must continue through one child; the recursive disjunction covers precisely those options with the correct remaining sum. Finite subtree descent guarantees termination.

Time and space

O(n) worst-case time and O(h) recursive stack space. Early success can avoid exploring the other subtree.

Common mistakes

Accepting remaining==0 before checking leaf status permits incomplete paths. Rejecting negative remainders loses paths containing later negative values.

Reasoning card

State: has_path_sum(node,remaining) asks whether a path starting at node and ending at a leaf contributes exactly remaining.

Invariant: Remaining target is what the unfinished path must contribute.

Decision to rehearse: Subtract current value before delegating; succeed only at a leaf.

Finish: Otherwise ask either child to fulfill the new remainder

Transfer exercise

Enumerate all matching paths, adding choose-explore-undo path ownership to the same remaining-sum contract.