Root to Node Path
Given the root of a binary tree and a target value, return the sequence of node values along the path from the root down to the node holding that value, root first and target last. The target is guaranteed to exist. If several nodes hold the same value, returning the path to any one of them is acceptable. A target sitting at the root returns a single-element list.
- The number of nodes in the tree is in the range [1, 1000]
- -1000 <= Node.val <= 1000
- The target value is guaranteed to exist in the tree
- Values are not guaranteed to be distinct
root = [1,2,3,4,5], target = 5[1,2,5]root = [1,2,3,4,5], target = 1[1]root = [1,2,3,4,5], target = 3[1,3]root = [1,2,2,4], target = 2[1,2]A tree has no upward links, so you cannot start at the target and climb. You have to start at the root and go looking — and since there is exactly one downward route to any node, whichever route succeeds is the answer.
The shape is the backtracking walk from Binary Tree Paths, with one important difference. There, every leaf produced an answer, so the walk always ran to completion. Here at most one node is the target, so the moment it is found the search is over and the current contents of the path list are precisely what we want. The interesting question becomes: how does a node know whether it belongs in the answer?
Sitting on some node, you cannot tell yet. The target might be in your left subtree, in your right subtree, or nowhere below you at all — and you only learn which after asking. So the honest statement of one node's job is:
found(node) = (node is the target) OR found(node.left) OR found(node.right)and found(null) = false, since an empty subtree contains nothing. If any of those three is true, this node lies above the target (or is it) and must appear in the result. If all three are false, this node is on a dead branch and must not appear.
That gives the algorithm its two-sided structure. On the way in we do not know the answer yet, so we add ourselves speculatively. On the way out we do know, so we either keep the entry — by reporting success upward — or retract it.
path = []
def find(node, target):
if node is None:
return False # nothing here, and nothing was added
path.append(node.val) # speculative: assume this node is on the route
if node.val == target:
return True # found — leave the path exactly as it is
if find(node.left, target) or find(node.right, target):
return True # the target is below me, so I stay on the path
path.pop() # dead end — retract myself
return False
find(root, target)
return pathreturn True deliberately skips the pop, and every failure path performs exactly one. That asymmetry is the whole mechanism. On success the list is frozen mid-traversal holding root-to-target, and the True propagates upward so no ancestor pops either. Add a pop before returning True and the answer dismantles itself on the way out; forget the pop on failure and abandoned branches stay glued to the result. Count them once when you write this: one push per entry, one pop per failed exit.The second thing the or buys you is early exit. Python's or does not evaluate its right side when the left is already true, so once the left subtree reports success the right subtree is never touched at all — and the same short-circuit ripples up through every ancestor, ending the traversal on the spot.
Node 4 is the case worth studying: it was on the list for a while and then removed. Speculate, then retract — that is what backtracking means, and the traversal had to visit 4 to learn it was useless.
In the worst case the target sits in the last place looked, so every node is visited once: O(N) time. The extra space is the recursion stack plus the path list, both bounded by the height: O(H). Early exit does not change the worst case but often helps a great deal in practice.
Two habits are worth extracting. First, when a node's membership in the answer depends on something discovered below it, add speculatively on the way down and retract on the way up — you will use that in Path Sum II, in subset and permutation generation, and in every maze-style search. Second, notice that this search returns a boolean upward and leaves its real output in a shared structure. That split — a cheap signal in the return value, the substance kept on the side — is the same arrangement as Diameter's running maximum. Lowest Common Ancestor takes this idea one step further: instead of a boolean it returns the found node itself, which turns "did you find it?" into "what did you find?" and unlocks a much slicker solution.
Backtracking Trace Optimizer
Starting at Root. Goal: Find Node 5.
path.push(current)path.pop() // Remove lastStrategy
Focus on the recursive nature of trees: solve for subtrees and combine results at the root.
"Divide and Conquer: Subproblem → Recurrence → Result"