Root to Leaf Paths
Root to Leaf Paths is a medium trees & bst problem solved with the backtracking pattern.
The best approach, backtracking with one shared list, runs in O(n · h) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from copy the path at each level up.
Problem
Return every path from the root to a leaf as a list of node values, ordered from the leftmost leaf to the rightmost.
Examples
Example 1
- Input
root = [1, 2, 3, 4, 5]- Output
[[1,2,4],[1,2,5],[1,3]]
Example 2
- Input
root = [8]- Output
[[8]]
Constraints
- The tree has
1to10^4nodes. - Return the paths from left to right.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Copy the path at each level | O(n · h) | O(n · h) |
| Backtracking with one shared list | O(n · h) | O(h) |
1Copy the path at each level
O(n · h)O(n · h)Pass a fresh copy of the path to every child. Simple, but copies at every node.
- newPath = copy(path) + node.val; at a leaf, record newPath.
- Recurse left and right with newPath.
class Solution {
public List<List<Integer>> paths(TreeNode root) {
List<List<Integer>> out = new ArrayList<>();
dfs(root, new ArrayList<>(), out);
return out;
}
private void dfs(TreeNode node, List<Integer> path, List<List<Integer>> out) {
if (node == null) return;
List<Integer> p = new ArrayList<>(path);
p.add(node.val);
if (node.left == null && node.right == null) { out.add(p); return; }
dfs(node.left, p, out);
dfs(node.right, p, out);
}
}class Solution:
def paths(self, root: Optional[TreeNode]) -> List[List[int]]:
out: List[List[int]] = []
self.dfs(root, [], out)
return out
def dfs(self, node: Optional[TreeNode], path: List[int], out: List[List[int]]) -> None:
if node is None:
return
p = path[:]
p.append(node.val)
if node.left is None and node.right is None:
out.append(p)
return
self.dfs(node.left, p, out)
self.dfs(node.right, p, out)class Solution {
public:
vector<vector<int>> paths(TreeNode* root) {
vector<vector<int>> out;
dfs(root, vector<int>(), out);
return out;
}
private:
void dfs(TreeNode* node, const vector<int>& path, vector<vector<int>>& out) {
if (node == nullptr) return;
vector<int> p(path);
p.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) { out.push_back(p); return; }
dfs(node->left, p, out);
dfs(node->right, p, out);
}
};function paths(root) {
const out = [];
dfs(root, [], out);
return out;
}
function dfs(node, path, out) {
if (node === null) return;
const p = [...path];
p.push(node.val);
if (node.left === null && node.right === null) { out.push(p); return; }
dfs(node.left, p, out);
dfs(node.right, p, out);
}2Backtracking with one shared list
O(n · h)Copying each root-to-leaf path costs up to h.O(h)Recursion depth and the path, not counting the output.Share one path list. Add the node, record a copy at a leaf, recurse into the children and remove the node before returning.
- path.add(val).
- Leaf: out.add(copy(path)). Else recurse left, right.
- path.remove(last).
class Solution {
public List<List<Integer>> paths(TreeNode root) {
List<List<Integer>> out = new ArrayList<>();
dfs(root, new ArrayList<>(), out);
return out;
}
private void dfs(TreeNode node, List<Integer> path, List<List<Integer>> out) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null) out.add(new ArrayList<>(path));
else {
dfs(node.left, path, out);
dfs(node.right, path, out);
}
path.remove(path.size() - 1);
}
}class Solution:
def paths(self, root: Optional[TreeNode]) -> List[List[int]]:
out: List[List[int]] = []
self.dfs(root, [], out)
return out
def dfs(self, node: Optional[TreeNode], path: List[int], out: List[List[int]]) -> None:
if node is None:
return
path.append(node.val)
if node.left is None and node.right is None:
out.append(path[:])
else:
self.dfs(node.left, path, out)
self.dfs(node.right, path, out)
path.pop()class Solution {
public:
vector<vector<int>> paths(TreeNode* root) {
vector<vector<int>> out;
vector<int> path;
dfs(root, path, out);
return out;
}
private:
void dfs(TreeNode* node, vector<int>& path, vector<vector<int>>& out) {
if (node == nullptr) return;
path.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) out.push_back(path);
else {
dfs(node->left, path, out);
dfs(node->right, path, out);
}
path.pop_back();
}
};function paths(root) {
const out = [];
dfs(root, [], out);
return out;
}
function dfs(node, path, out) {
if (node === null) return;
path.push(node.val);
if (node.left === null && node.right === null) out.push([...path]);
else {
dfs(node.left, path, out);
dfs(node.right, path, out);
}
path.pop();
}Edge cases to test
- Single node
- Nodes with one child are not leaves
Hints
Hint 1
Add the node to the path, recurse, then remove it on the way back up.
FAQ
What is the best time complexity for Root to Leaf Paths?
Backtracking with one shared list runs in O(n · h) time and O(h) extra space. Copying each root-to-leaf path costs up to h.
Which pattern does Root to Leaf Paths use?
It is a trees & bst problem that uses the backtracking pattern. Other problems with the same pattern: Path Sum II, Path Sum III.
Is there a brute force solution for Root to Leaf Paths?
Yes. Copy the path at each level takes O(n · h) time and O(n · h) space. Pass a fresh copy of the path to every child.
Which edge cases should I test for Root to Leaf Paths?
Single node; Nodes with one child are not leaves.