Trace the Route From the Root to a Chosen Node
Solve this ProblemYou are given the root of a binary tree in which every node has a distinct value, and an integer target. Return the list of node values on the route from the root down to the node holding target, starting with the root's value and ending with target. If the tree has no node with that value, return an empty list.
A depth-first search with backtracking finds the route directly: keep a path, add a node when you enter it, and take it off again when the target is not below it.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
1 ≤ node.val ≤ 1000, and all node values in the tree are distinct; 1 ≤ target ≤ 1000 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Return the values on the route from the root down to the node whose value is target (both ends included), in order from the root. If no node has that value, return an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Record Every Parent, Then Climb Up From the Target
GoodSweep the whole tree level by level and, for every node, remember its parent in a map (the root's parent is a sentinel 0, safe because values start at 1). If the target never appears as a key, there is no route. Otherwise climb: start at the target, repeatedly jump to its parent until the sentinel is reached, collecting the values on the way, and reverse the list so it reads from the root down. It always builds the parent map for all n nodes — even if the target is the root itself — so time and space are both O(n).
O(n)O(n)1class Solution {
2 public List<Integer> routeTo(TreeNode root, int target) {
3 List<Integer> route = new ArrayList<>();
4 if (root == null) return route;
5 Map<Integer, Integer> parent = new HashMap<>();
6 parent.put(root.val, 0);
7 Queue<TreeNode> queue = new ArrayDeque<>();
8 queue.add(root);
9 while (!queue.isEmpty()) {
10 TreeNode node = queue.poll();
11 if (node.left != null) {
12 parent.put(node.left.val, node.val);
13 queue.add(node.left);
14 }
15 if (node.right != null) {
16 parent.put(node.right.val, node.val);
17 queue.add(node.right);
18 }
19 }
20 if (!parent.containsKey(target)) return route;
21 for (int v = target; v != 0; v = parent.get(v)) route.add(v);
22 Collections.reverse(route);
23 return route;
24 }
25}Optimal — Depth-First Search With Backtracking
OptimalWalk down with one shared path. Entering a node appends its value. If it is the target, we are done and the path (root to target) is exactly the answer. Otherwise try the left child, then the right child; if either finds the target, report success upward without touching the path. If neither does, this node is on no route to the target, so remove its value (backtrack) and report failure. When the search finishes without success, every value has been removed and the path is empty — precisely the "no route" answer. The search stops at the first hit, and only the path and recursion use extra space: O(h).
O(n)O(h)1class Solution {
2 public List<Integer> routeTo(TreeNode root, int target) {
3 List<Integer> path = new ArrayList<>();
4 find(root, target, path);
5 return path;
6 }
7
8 private boolean find(TreeNode node, int target, List<Integer> path) {
9 if (node == null) return false;
10 path.add(node.val);
11 if (node.val == target) return true;
12 if (find(node.left, target, path) || find(node.right, target, path)) return true;
13 path.remove(path.size() - 1);
14 return false;
15 }
16}