☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Print root to leaf path in BT

Medium TUF ID 122 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree. Return every path that starts at the root and ends at a leaf (a node with no children). Each path is the list of node values along it, and the paths are listed in left-to-right order of their leaves. An empty tree has no paths.

LeetCode’s version asks for each path as a string such as "1->2->5"; joining each list with "->" gives exactly that. Striver’s sheet also uses this row for the closely related task “return the path from the root to a given node”, so a short section at the end covers that variant with the same technique.

Constraints: up to 10^5 nodes; values are integers and may repeat.

Example 1

      1
    /   \
   2     3
    \
     5

answer = [[1, 2, 5], [1, 3]]

2 is not a leaf because it has a right child, so [1, 2] is not a path. The leaves are 5 and 3.

Example 2

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

answer = [[1, 2, 4], [1, 2, 5], [1, 3, 6], [1, 3, 7]]

Four leaves give four paths.

Approach 1: Copy the path into every call

Intuition. A depth-first walk visits the nodes of a path in the order they appear on it. If every recursive call receives “the path from the root down to my parent”, it only has to add its own value. When the current node is a leaf, the path is complete and goes into the answer.

The simplest way to make this correct is to give every call its own copy of the path. Then siblings cannot interfere with each other: whatever the left child adds lives in the left child’s copy, and the right child never sees it. No undo step is needed.

Algorithm.

  1. Start with an empty path at the root.
  2. At each non-null node: copy the incoming path, add the node’s value.
  3. If the node is a leaf, add the copy to the answer and return.
  4. Otherwise recurse into the left child, then the right child, passing the copy.
static List<List<Integer>> bruteForce(TreeNode root) {
    List<List<Integer>> paths = new ArrayList<>();
    copyDfs(root, new ArrayList<>(), paths);
    return paths;
}

static void copyDfs(TreeNode node, List<Integer> pathSoFar, List<List<Integer>> paths) {
    if (node == null) return;
    List<Integer> path = new ArrayList<>(pathSoFar);          // every call owns its own copy
    path.add(node.val);
    if (node.left == null && node.right == null) { paths.add(path); return; }
    copyDfs(node.left, path, paths);
    copyDfs(node.right, path, paths);
}

Complexity. Time O(n * h): every node copies a path of length up to h, the height of the tree. Space O(n * h) in total allocations; at any moment the recursion stack holds up to h copies of length up to h, so O(h^2) live memory besides the answer.

Approach 2: Optimal, backtracking with one shared path

Intuition. Most of those copies are wasted: an internal node’s copy is never stored anywhere. We can share one list for the whole walk if we keep a simple promise: every call leaves the path exactly as it found it. A call appends its value on entry and removes it right before returning. Then when the left child returns, the path again ends at the current node, and the right child can append to it safely.

We copy only at a leaf, because the shared list keeps changing after that moment and the answer needs a frozen snapshot.

Algorithm.

  1. Keep one list path.
  2. At each non-null node: append its value.
  3. If it is a leaf, add a copy of path to the answer. Otherwise recurse left, then right.
  4. Remove the last element of path (the value appended in step 2).
static List<List<Integer>> optimal(TreeNode root) {
    List<List<Integer>> paths = new ArrayList<>();
    backtrack(root, new ArrayList<>(), paths);
    return paths;
}

static void backtrack(TreeNode node, List<Integer> path, List<List<Integer>> paths) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null) {
        paths.add(new ArrayList<>(path));                     // snapshot: path keeps changing after this
    } else {
        backtrack(node.left, path, paths);
        backtrack(node.right, path, paths);
    }
    path.remove(path.size() - 1);                             // undo before returning to the parent
}

Dry run on Example 1:

step node path after the step answer
enter 1 [1] []
enter 2 [1, 2] []
enter 5 (leaf) [1, 2, 5] [[1, 2, 5]]
leave 5 [1, 2]  
leave 2 [1]  
enter 3 (leaf) [1, 3] [[1, 2, 5], [1, 3]]
leave 3 [1]  
leave 1 []  

The left child of 2 is null, so that call returns immediately without touching the path.

Complexity. Time O(n + L * h), where L is the number of leaves: the walk itself is O(n), and each of the L snapshots copies at most h values. The L * h part is the size of the output, so no algorithm can do better. Extra space O(h) for the shared path and the recursion stack.

Variant: path from the root to one given node

Intuition. Sometimes we want only the path to a specific value (for instance, as a building block for finding the lowest common ancestor). The same append-then-undo walk works with one change: the function returns true when it has found the target. As soon as any call returns true, every caller above it returns true immediately without removing its value, so the path stays intact. A call that finds nothing in either subtree removes its value and returns false.

static List<Integer> pathToNode(TreeNode root, int target) {
    List<Integer> path = new ArrayList<>();
    findPath(root, target, path);
    return path;
}

static boolean findPath(TreeNode node, int target, List<Integer> path) {
    if (node == null) return false;
    path.add(node.val);
    if (node.val == target) return true;
    if (findPath(node.left, target, path) || findPath(node.right, target, path)) return true;
    path.remove(path.size() - 1);                             // target is not below this node
    return false;
}

On Example 2 with target 5, the walk enters 1, 2, 4 (no match, removed), then 5 (match). The answer is [1, 2, 5]. If the target is absent, every value gets removed and the result is an empty list. This runs in O(n) time and O(h) space.

Edge cases and pitfalls