Root to Node Path in a Binary Tree
Find the exact path from root to target node using DFS and backtracking.
Key concepts at a glance — for those who already know the basics.
Problem Statement
Given a binary tree root and a target value, return the path from root to target node.
Example: target = 7, path = [1,2,5,7]
01 · The core idea
Keep one shared path list. Push on entry, recurse, and pop only when that branch fails.
The path list mirrors the recursion stack from root to current node.
02 · Why backtracking matters
Correct branch
Keep nodes in path while bubbling true from target.
Wrong branch
Pop node before returning false to clean stale path entries.
03 · How to think
Enter node and push to path
At each DFS call, append current node value to path.
If node is target, stop immediately
Return true and bubble success back up the recursion stack.
Try left, then right
If either subtree returns true, keep current node in path.
Backtrack on failure
If both sides fail, pop current node and return false.
04 · Diagram
Target: 7, final path: [1,2,5,7]
05 · Code
def rootToNodePath(root, target):
path = []
def dfs(node):
if not node:
return False
path.append(node.val)
if node.val == target:
return True
if dfs(node.left) or dfs(node.right):
return True
path.pop() # backtrack
return False
return path if dfs(root) else []06 · Complexity
Time
O(n)
Every node is visited at most once.
Space
O(h)
Recursion depth and path size are bounded by tree height.
07 · Interview uses
LCA and path-based tree questions: Many LCA variants compute root-to-node paths first and compare them.
Path sum and root-to-leaf problems: Same DFS + backtracking skeleton, with different success conditions.
Tree navigation features: Useful in editors/visualizers where selected node breadcrumbs are needed.
Backtracking fundamentals: This is a canonical example of choice, recurse, undo pattern.
Ready to see it in action?
Step through the visualizer to watch the algorithm state update live.