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

Enter fullscreen mode Exit fullscreen mode

Pattern Recognition

Whenever you see:

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

Think:

DFS + Backtracking

Key Observation

Maintain:

Current Path

Enter fullscreen mode Exit fullscreen mode

Whenever:

Leaf Node

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Step 3

Explore:

Left

↓

Right

Enter fullscreen mode Exit fullscreen mode

Step 4

Backtrack.

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

Enter fullscreen mode Exit fullscreen mode

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);
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

        1
       / \
      2   3
     /
    4

Enter fullscreen mode Exit fullscreen mode

Current Path:

1

Enter fullscreen mode Exit fullscreen mode

↓

1 2

Enter fullscreen mode Exit fullscreen mode

↓

1 2 4

Enter fullscreen mode Exit fullscreen mode

Leaf:

Store:

[1,2,4]

Enter fullscreen mode Exit fullscreen mode

Backtrack:

1 2

Enter fullscreen mode Exit fullscreen mode

↓

1

Enter fullscreen mode Exit fullscreen mode

↓

Explore:

3

Enter fullscreen mode Exit fullscreen mode

Store:

[1,3]

Enter fullscreen mode Exit fullscreen mode

Final Answer:

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

DFS

↓

Path

↓

Leaf

↓

Answer

↓

Backtrack

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Print all root-to-leaf paths”

your brain should immediately think:

DFS + Backtracking