Algorithm

Root to Node Path

Trees Pattern

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.

CONSTRAINTS
  • 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
EXAMPLE 1
Input: root = [1,2,3,4,5], target = 5
Output: [1,2,5]
5 hangs under 2, which hangs under the root, and there is exactly one downward route to any node in a tree — so this path is the only possible answer.
EXAMPLE 2
Input: root = [1,2,3,4,5], target = 1
Output: [1]
The target is the root itself, so the path has zero edges and one node. A result of [] would wrongly suggest the target was not found.
EXAMPLE 3
Input: root = [1,2,3,4,5], target = 3
Output: [1,3]
The whole left subtree is searched first and comes back empty-handed; that exploration contributes nothing to the answer, which contains only the nodes actually above 3.
EXAMPLE 4
Input: root = [1,2,2,4], target = 2
Output: [1,2]
Two nodes hold the value 2. Either path is acceptable; a left-first search finds the left one, and its path happens to be [1,2] in both cases here.
What if several nodes share the target value?
Any one of their paths is fine unless the interviewer says otherwise. A left-first depth-first search returns the leftmost, deepest-first match it reaches.
What should happen if the target is absent?
The constraints promise it exists, but say aloud what you would do otherwise — returning an empty list is the usual contract, and it needs the search to report failure honestly rather than leaving a half-built path behind.
Should the path include the target node itself?
Yes, at the end, and the root at the start. Both endpoints are included.
Can I search by node reference instead of value?
If the interviewer hands you the node object, comparing references is safer — it sidesteps the duplicate-value ambiguity entirely, which is exactly what Lowest Common Ancestor does.

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?

A node belongs on the path only if the target lies beneath it

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:

text
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.

python
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 path
Crucial Noteevery return 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.

Worked example:root 1 with children 2 and 3; 2 has children 4 and 5; target 5
- At 1: push 1, path = [1]. Not the target. Search left.
- At 2: push 2, path = [1, 2]. Not the target. Search left.
- At 4: push 4, path = [1, 2, 4]. Not the target. Both children are null and return false. Dead end — pop 4, path back to [1, 2], report false.
- Back at 2, the left call failed, so try the right. At 5: push 5, path = [1, 2, 5]. It is the target — return true without popping.
- 2 sees true from its right call and returns true immediately, keeping 2 in the list. 1 sees true from its left call and does the same. Node 3 is never visited.
- The path list still holds [1, 2, 5]. That is the answer.

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.

Cost, and the reflex

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.

Interactive Strategy Visualization

Backtracking Trace Optimizer

Recursive State Recovery
12345
Path Buffer:
1
Push
Backtracking Strategy

Starting at Root. Goal: Find Node 5.

State Mutation Memory
path.push(current)
path.pop() // Remove last
Efficiency Note
Pass list by reference to avoid O(N^2) path copying.

Strategy

Focus on the recursive nature of trees: solve for subtrees and combine results at the root.

"Divide and Conquer: Subproblem → Recurrence → Result"

O(N × H) Store Every Root-to-Leaf Path
O(N) Time · O(H) Space Backtracking With Early Exit