Return the values along the path from the root down to the first node holding
target, inclusive. If the target isn't in the tree, return an empty slice.
treePathFinder(root, target)
Input format: tree | target. Output the path values space-separated (empty
line if not found).
(3 9 20 x x 15 7), 15 // → 3 20 15
(3 9 20 x x 15 7), 9 // → 3 9
(3 9 20 x x 15 7), 42 // → (empty)
This asks for more than yes/no (like a plain "does the tree contain the target" search) — it wants the actual sequence of values from root to wherever the target lives. That changes what each call needs to hand back: not just found/not-found, but the path itself when found.
For any node: is there a path from here to the target, and if so, what is it? Three cases: an empty subtree has no path — "not found." If this node's value is the target, the path is just this one node. Otherwise the target, if reachable, lies in the left or right subtree — ask each child the same question.
A natural instinct is to build the path by appending as you descend, passing a growing list down through the calls. That works, but every call has to carry and mutate shared state, and discard it on dead ends. Cleaner: build nothing on the way down. Each call returns either "not found" or the complete path from itself to the target, and each parent, seeing a non-empty path from a child, prepends its own value to the front before returning it up. By the time the recursion unwinds, the path is assembled correctly — only along the branch that actually led to the target.
Checking the left subtree fully before trying the right, and returning immediately on success, guarantees a well-defined answer. If both checks happened unconditionally and results were combined carelessly, you could overwrite a valid answer or leave the choice ambiguous.
Worst case, every node is visited once, so time is proportional to the number of nodes. Prepending only happens along the single successful branch, adding no cost beyond the traversal.
def tree_path_finder(root, target):
if root is None:
return None
if root.val == target:
return [root.val]
l = tree_path_finder(root.left, target)
if l is not None:
return [root.val] + l
r = tree_path_finder(root.right, target)
if r is not None:
return [root.val] + r
return None
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.