DFS the tree with a running sum; light up any root-to-leaf path that hits the target.
Given a binary tree and a target integer, determine whether the tree has a root-to-leaf path whose node values sum to the target. A leaf is a node with no children. The algorithm performs a depth-first traversal, accumulating the running sum as it descends; when a leaf is reached it checks whether the accumulated sum equals the target.
At each node, add its value to the running sum and recurse into the left and right subtrees. The accumulator travels down each branch, so you never need to subtract while going deeper; subtraction happens implicitly when a branch finishes and the call stack unwinds (backtrack).
A node is a leaf when both its left and right children are null. Only at a leaf do we compare the accumulated sum to the target. If sum === target the path is a match. If the node has at least one child we continue descending. No check is performed mid-path.
Every node is visited exactly once so time is O(n). The recursion stack can grow as deep as the tree height, so space is O(h). For a balanced tree h = O(log n); for a skewed tree h = O(n). No auxiliary data structures are allocated beyond the call stack.
Variants include "Path Sum II" (collect all matching paths) and "Path Sum III" (any node-to-node path, not just root-to-leaf). The core technique (DFS with a running accumulator) applies to all of them.