Path sum

Does some root-to-leaf path add up to a target value?

The idea

Subtract the current node's value from the target as the search goes down, so by the time a leaf is reached, the question is simply whether the remaining target equals that leaf's value. Try the left subtree with the reduced target, then the right subtree, and the answer is true the moment either one succeeds.

Code

public static bool HasPathSum(TreeNode node, int target) {
    if (node == null) return false;
    if (node.left == null && node.right == null) return target == node.val;
    int remaining = target - node.val;
    return HasPathSum(node.left, remaining) || HasPathSum(node.right, remaining);
}

Tips

• Checking isLeaf (no left and no right child) matters: a path must end at a leaf, not just stop early at any node that happens to sum correctly.

In the .NET library

This "carry a running total down the recursion" idea generalises directly to listing every qualifying path, not just testing whether one exists, by appending to a list instead of returning a bool.