Root to Leaf Path

Problem Statement

Given the root of a binary tree, print all root-to-leaf paths.

A path starts at the root and ends at a leaf node.

---

Brute Force Intuition

In an interview, you can explain it like this:

Traverse the tree while maintaining the current path. Whenever a leaf node is reached, store the path.

Since every node belongs to exactly one traversal path, DFS naturally fits.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(H)

---

Moving Towards the Optimal Approach

Observe that a path changes while moving down the tree.

Whenever recursion returns,

the last node should be removed.

This is exactly:

Backtracking

---

Pattern Recognition

Whenever you see:

• Root to Leaf
• Generate All Paths
• Explore Every Possibility

Think:

DFS + Backtracking

---

Key Observation

Maintain:

Current Path

Whenever:

Leaf Node

is reached,

store a copy of the path.

After exploring,

remove the current node.

---

Optimal Approach

Step 1

Add current node.

---

Step 2

If leaf:

Store Path

---

Step 3

Explore:

Left

↓

Right

---

Step 4

Backtrack.

path.remove(path.size()-1);

---

Optimal Java Solution

class Solution {

    public static ArrayList<ArrayList<Integer>>
    Paths(Node root) {

        ArrayList<ArrayList<Integer>> ans =
                new ArrayList<>();

        dfs(root,
            new ArrayList<>(),
            ans);

        return ans;
    }

    static void dfs(Node root,
                    ArrayList<Integer> path,
                    ArrayList<ArrayList<Integer>> ans) {

        if (root == null)
            return;

        path.add(root.data);

        if (root.left == null &&
            root.right == null) {

            ans.add(new ArrayList<>(path));

        } else {

            dfs(root.left, path, ans);

            dfs(root.right, path, ans);
        }

        path.remove(path.size() - 1);
    }
}

---

Dry Run

        1
       / \
      2   3
     /
    4

Current Path:

1

↓

1 2

↓

1 2 4

Leaf:

Store:

[1,2,4]

Backtrack:

1 2

↓

1

↓

Explore:

3

Store:

[1,3]

Final Answer:

[[1,2,4],[1,3]]

---

Why Backtracking Works?

Every recursive call adds one node to the path.

Once that subtree is completely explored,

the node is removed,

allowing the same path list to be reused for other branches.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

---

Interview One-Liner

Use DFS with backtracking by maintaining the current path, storing it at every leaf node, and removing the node while returning from recursion.

---

Pattern Learned

DFS

↓

Current Path

↓

Leaf

↓

Store Copy

↓

Backtrack

Similar Problems

• Root to Leaf Paths
• Path Sum II
• Binary Tree Paths
• Subsets
• Combination Sum

---

Memory Trick

Think:

Visit Node

↓

Add To Path

↓

Leaf?

↓

Store Copy

↓

Remove Node

Mental Model

DFS

↓

Path

↓

Leaf

↓

Answer

↓

Backtrack

Whenever you hear:

"Print all root-to-leaf paths"

your brain should immediately think:

DFS + Backtracking