Start practising

Root to Leaf Paths

Medium Trees & BST Backtracking Original on GeeksforGeeks

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, 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 1 to 10^4 nodes.
  • Return the paths from left to right.

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 Java code.

ApproachTimeSpace
Copy the path at each levelO(n · h)O(n · h)
Backtracking with one shared listO(n · h)O(h)

1Copy the path at each level

TimeO(n · h)
SpaceO(n · h)

Pass a fresh copy of the path to every child. Simple, but copies at every node.

  1. newPath = copy(path) + node.val; at a leaf, record newPath.
  2. Recurse left and right with newPath.
Java
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);
    }
}

2Backtracking with one shared list

TimeO(n · h)Copying each root-to-leaf path costs up to h.
SpaceO(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.

  1. path.add(val).
  2. Leaf: out.add(copy(path)). Else recurse left, right.
  3. path.remove(last).
Java
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);
    }
}

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.

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.