Path Sum Problems

As you descend the tree, subtract each node's value from the remaining target. When you reach a leaf, the path is valid exactly when the remaining target is zero. The subtlety is that only leaves count: a node whose remaining target happens to be zero but which still has children is not the end of a valid path, because the problem asks for root to leaf paths.

So the check for success must be made only when the node has no children, and otherwise you keep descending. This is the mistake that produces wrong answers: returning true as soon as the running sum equals the target, without checking whether you are at a leaf.

The mechanism is that the remaining target is the running state carried down the tree. Each level reduces it by the node's value, so at a leaf the remaining target is the target minus the sum of the path, and a zero remaining target means the path sums exactly.

The trade-off to name is the shape of the answer. If the question asks whether such a path exists, a boolean is enough and the recursion can stop at the first hit, which makes it much faster than the version that collects all paths. If it asks for all the paths, you have to keep going and you also have to copy the path list when you record it, because the same list is mutated as the recursion unwinds. A third variant asks for the count of such paths, which is the same traversal with a counter instead of a list.

Subtract each node's value from the target as you descend, and only succeed at a leaf.

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


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


tree = TreeNode(5, TreeNode(4, TreeNode(3), TreeNode(2)), TreeNode(8))
print(has_path_sum(tree, 12))
print(has_path_sum(tree, 9))

The outputs are True and False. The path 5, 4, 3 sums to twelve, so the first call succeeds. No path sums to nine, so the second fails.

The mechanism is that the target shrinks as the tree is descended, so the check at each leaf is a single comparison against the remaining amount. The or between the two recursive calls means the search stops as soon as one branch succeeds, which is why the boolean version is much cheaper than collecting every path.

The trade-off to name is that this version visits at most every node once, but it cannot stop early inside a subtree that fails, since the recursion always explores both children of every non-leaf. That is unavoidable for the boolean question in general. The other detail is that the empty tree returns false, which is right because there is no path at all, and the leaf check compares against the reduced target rather than the original one, which is the whole point of passing the reduced value down.