Root-to-leaf paths
Walk down a tree while keeping the path from the root to the current node, and act on it whenever you reach a leaf.
O(n * h)Space O(h)8 practice problemsStep-through pictureThe idea
A root-to-leaf path is the list of nodes you pass going from the root down to a leaf, a node with no children. A tree has exactly one such path per leaf. Breadcrumbs in a menu and file paths in a folder tree are root-to-leaf paths.
To list them all, walk the tree depth-first and keep the current path in an array called path. When you step into a node, add it to the end. When you finish with it, remove it. This undo step is called backtracking: it puts path back the way the parent had it, so the parent can try its next child.
At a leaf, path holds exactly the route from the root to that leaf, so you can save a copy, check its sum, or build a string from it.
An everyday example
Writing down the trail on a hike
You hike a trail system where every fork splits into smaller trails. You write each landmark on a notepad as you pass it. When a trail ends, you photograph your notepad: that photo is one complete route. Then you walk back to the last fork, crossing off the landmarks you are leaving, and try the other trail.
| In the example | In the code |
|---|---|
| The notepad | path |
| Writing down a landmark | path.push(node.val) |
| A trail that ends | node.left === null && node.right === null |
| Photographing the notepad | paths.push([...path]) |
| Crossing off a landmark when you walk back | path.pop() |
From the slow way to root-to-leaf paths
- A slow way to list every root-to-leaf path: first find every leaf, then for each leaf search the tree again for the route that reaches it. With many leaves, that's many full searches of up to
nnodes each,O(n²)in total. - But a depth-first walk already passes along every route. While the walk is standing on a node, the calls waiting on the call stack are exactly that node's ancestors, in order from the root. The route is already there; we only need to write it down.
- Keep it in one shared array,
path. Entering a node pushes its value, sopathgrows as the walk goes down. Leaving a node must undo that push, so that the parent sees its own route again before it walks into its next child. This push-then-pop pattern is called backtracking. - When the walk stands on a leaf,
pathis a complete route from the root, so save a copy of it, because the array itself keeps changing. One DFS with a shared array, a push on entry, a copy at each leaf, and a pop on exit: that's root-to-leaf path listing.
How it works
- Keep
pathsfor the answers and one sharedpathfor the current route. - In
walk(node), stop atnull. - Add the node:
path.push(node.val). - If the node is a leaf, save a copy of
pathintopaths. - Otherwise walk into
node.leftand thennode.right. - Before returning, remove the node again with
path.pop(), so the parent's path is unchanged.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function rootToLeafPaths(root) {const paths = [];const path = [];function walk(node) {if (node === null) return;path.push(node.val);if (node.left === null && node.right === null) {paths.push([...path]);} else {walk(node.left);walk(node.right);}path.pop();}walk(root);return paths;}
How fast it is
| Time | O(n * h) |
|---|---|
| Extra memory | O(h) |
The walk visits each node once. Saving a path copies up to h values, once per leaf. The shared path and the call stack hold at most one route, not counting the answer.
- Best case
O(n)A chain: there is only one leaf, so one copy of length
nis made, plus thenvisits. - Average case
O(n log n)A balanced tree: about
n / 2leaves, each copied with a route of aboutlog₂ nvalues. - Worst case
O(n · h)A chain of
n / 2nodes where each node also has a leaf hanging off its side. The routes have lengths 2, 3, 4, and so on, so the copies add up to aboutn² / 8values.
Common mistakes
- Saving
pathitself instead of a copy. Every saved route is the same array, which is empty at the end. Save[...path]. - Forgetting
path.pop(). Nodes from finished branches stay in the route and later paths come out too long. - Treating a node with one child as a leaf. A leaf has no children at all; check both
leftandright. - Saving at
nullinstead of at a leaf. A node with one child would then be saved as if a path ended there.
When to use it
Look for these clues in a problem:
- The question mentions paths "from the root to a leaf", breadcrumbs, or full file paths.
- You must find whether some root-to-leaf path has a given sum, or list all that do.
- Each path forms something, like a number from its digits or a string from its labels.
- The answer depends on all the ancestors of a node, not only its parent.
Check yourself
Answer each one in your head first, then open it.
Why is [...path] needed at a leaf?
path is one array that keeps changing. Saving it directly saves a reference to it, and every saved entry ends up as the final empty array.
How many routes are saved for a tree with n nodes and k leaves?
Exactly k, one per leaf. Nodes with children never trigger a save.
In the trace, what would paths be if line 13, path.pop(), were removed?
[[3, 8, 6], [3, 8, 6, 1, 2], [3, 8, 6, 1, 2, 9]]. Each route would keep every node visited before it.
Why doesn't a running sum passed as a parameter need to be undone?
Each call gets its own copy of the parameter. When a call returns, the parent's sum was never changed.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingmedium
Go further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The rule each call keeps: when walk(node) starts, path holds the values from the root down to node's parent, in order, and when it returns, path is exactly what it was when it started. For null, nothing is pushed or popped, so the rule holds.
For a real node, line 6 pushes node.val, so path is now the route from the root to node. If node is a leaf, that route is a root-to-leaf path and a copy is saved. If not, each child call starts with the right route and, by the same rule, gives it back unchanged. Then line 13 pops the one value this call pushed, restoring the starting state.
The DFS reaches every leaf exactly once, and at that moment path is that leaf's full route, so each root-to-leaf path is saved once. Nothing else is saved, because only leaves reach line 8. The walk ends like any DFS: each call goes one level deeper, and the depth is finite.
Going deeper
3 more ideas
Why one shared array is enough
Each call pushes exactly one value and pops exactly one value before it returns. So when a call ends, path is exactly what it was when the call started. That means the parent sees its own path again and can walk into its second child with the right route.
Carrying a running value instead
If you only need a total, you don't need the array. Pass the running sum as a parameter: walk(node, sum + node.val). Each call has its own copy of sum, so nothing needs to be undone. The same works for a number made of digits: value * 10 + node.val.
Time and memory
Walking takes O(n). Copying a path at a leaf costs its length, so listing all paths takes up to O(n * h) in total. The shared path and the call stack use O(h) memory, not counting the output.
Work it by hand
Every step in a table, with why
List every route in a 6-node tree with 3 leaves. Node 8 has only a right child, so it shows that only real leaves are saved.
root = [3, 8, 1, null, 6, 2, 9]
| Step | What happens | node.val | path | paths | Why |
|---|---|---|---|---|---|
| 1 | push | 3 | [3] | [] | Enter the root. 3 has children, so it isn't a leaf. |
| 2 | push | 8 | [3, 8] | [] | Go left to 8. It has a right child only. |
| 3 | push | 6 | [3, 8, 6] | [] | walk(8.left) returned at once on null, so the walk moved on to 8.right, which is 6. |
| 4 | leaf: save a copy | 6 | [3, 8, 6] | [[3, 8, 6]] | 6 has no children, so path is a full route and a copy is saved. |
| 5 | pop | 6 | [3, 8] | [[3, 8, 6]] | Leaving 6 removes it, giving 8 its route back. |
| 6 | pop | 8 | [3] | [[3, 8, 6]] | Both sides of 8 are done, so 8 is removed too. |
| 7 | push | 1 | [3, 1] | [[3, 8, 6]] | Back at the root, the walk enters its right child 1. |
| 8 | push | 2 | [3, 1, 2] | [[3, 8, 6]] | 1 has a left child 2. |
| 9 | leaf: save a copy | 2 | [3, 1, 2] | [[3, 8, 6], [3, 1, 2]] | 2 is a leaf, so its route is saved. |
| 10 | pop | 2 | [3, 1] | [[3, 8, 6], [3, 1, 2]] | Remove 2 before trying 1's right child. |
| 11 | push | 9 | [3, 1, 9] | [[3, 8, 6], [3, 1, 2]] | Because 2 was popped, 9 is added right after 1. Without the pop, this route would read [3, 1, 2, 9]. |
| 12 | leaf: save a copy | 9 | [3, 1, 9] | [[3, 8, 6], [3, 1, 2], [3, 1, 9]] | 9 is the last leaf. |
| 13 | pop | 9 | [3, 1] | 3 routes | Leave 9. |
| 14 | pop | 1 | [3] | 3 routes | Leave 1. |
| 15 | pop | 3 | [] | 3 routes | Leave the root. path is empty again, exactly as it was before the walk. |
[[3, 8, 6], [3, 1, 2], [3, 1, 9]], one route per leaf, from left to right. The trace ends when the root's call pops 3: 6 pushes and 6 pops, always in matching pairs.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Root-to-leaf paths | O(n · h) | O(h) | You need every route, or every route that passes a check. |
| Carry a value down | O(n) | O(h) | You only need a number per route, like a sum or a count, so no copies are made. |
| Search again for each leaf | O(n²) | O(h) | Never better. It's the slow start this walk replaces. |
| BFS with parent links | O(n · h) | O(n) | The tree is too deep for recursion. Record each node's parent during BFS, then rebuild each route by walking up from its leaf. |
Extra memory: O(h): the shared path and the call stack each hold at most one route. The output itself can reach O(n · h) values, as the worst case shows, and isn't counted here.
How the steps grow
- Root-to-leaf paths, Search again for each leaf, BFS with parent links
O(n · h) - Carry a value down
O(n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Root-to-leaf paths | 100 | 1 million | 1 trillion |
| Carry a value down | 10 | 1,000 | 1 million |
| Search again for each leaf | 100 | 1 million | 1 trillion |
| BFS with parent links | 100 | 1 million | 1 trillion |
Inputs that need care
5 tricky inputs
- An empty tree:
root = null walk(null)returns at once, sopathsstays[]. An empty tree has no routes.- One node:
root = [4] - The root is a leaf, so the answer is
[[4]]: one route of length one. - A node with only one child, like
8in the trace - It isn't a leaf, so nothing is saved there, and the missing side's call returns on
null. If you saved a route at everynullchild instead of at leaves,[3, 8]would be saved from8's empty left side and[3, 8, 6]would be saved twice. - Saving
pathinstead of[...path] - Every saved entry points to the same array, which is empty when the walk ends, so the answer would be
[[], [], []]. - Negative values in a target-sum version
- You can't stop early when the running sum passes the target, because a later negative value may bring it back down. Walk all the way to the leaf before deciding.
Variations and follow-ups
Twists interviewers add
Routes with a target sum
Carry the running sum as a parameter: walk(node, sum + node.val). At a leaf, save the route only if the sum equals the target. path still needs its push and pop, but the sum doesn't, because each call has its own copy.
Paths that start anywhere
To count downward paths with a given sum that may start below the root, keep a map from running sum to how many times it appears on the current route. At each node, add count.get(sum - target) to the answer, and undo the map change on the way back up, just like the pop.
Routes as strings
For breadcrumbs or file paths, build path.join(" / ") at each leaf. Or pass a string down, as in walk(node, prefix + "/" + node.val). Strings can't be changed in place, so no pop is needed, but each step copies the string.
Without recursion
Keep a stack of [node, routeSoFar] pairs, where each pair has its own route array. It uses more memory, but it handles trees too deep for the call stack.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "all paths", "root to leaf", "path sum", "print every route", or an answer that's a list of lists of node values.
- Say the backtracking rule: "every push has a matching pop before the call returns". Then point at where each one happens.
- Be exact about what a leaf is: both children are
null. Interviewers often use a tree whose root has one child to check this. - Expect "what if you only need to know whether some route adds up to the target?". Return a boolean, carry the sum, and stop at the first match:
return walk(node.left, s) || walk(node.right, s).
Where frontend code uses it
The same idea in real UI code
- Breadcrumb navigation shows the root-to-current path in a nested menu or category tree, like
Home / Shoes / Running. - Form libraries report validation errors with a path through nested data, like
address.street, built while walking the data down. - A file explorer search shows each matching file with its full path, the labels on the way from the root folder down to it.