Problem Description

You are given the root of a binary tree. Your task is to find all paths from the root node to any leaf node and return them as a list of strings.

A leaf node is defined as a node that has no children (both left and right children are null).

Each path should be represented as a string where:

• Node values are connected by the arrow symbol "->"
• The path starts from the root and ends at a leaf

For example, if you have a path from root with value 1, to a node with value 2, to a leaf with value 5, the path string would be "1->2->5".

The solution uses a depth-first search (DFS) approach with backtracking:

1. DFS Traversal: The algorithm explores each path from root to leaves recursively
2. Path Building: As we traverse down the tree, we add each node's value to a temporary list t
3. Leaf Detection: When we reach a leaf node (both left and right children are None), we convert the current path in t to a string with "->" as the separator and add it to our answer list
4. Backtracking: After exploring a node's subtrees, we remove the node's value from t using t.pop() to backtrack and explore other paths
5. Result: All collected root-to-leaf paths are returned as a list of strings

The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(n) for the recursion stack and storing the paths.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure, which is a hierarchical data structure with a root node and parent-child relationships.

DFS

• Yes: Since we identified this as a tree problem, the flowchart directs us to use DFS (Depth-First Search).

Conclusion: The flowchart suggests using a DFS approach for finding all root-to-leaf paths in the binary tree.

This makes perfect sense for our problem because:

1. We need to explore each complete path from root to leaf before moving to the next path
2. DFS naturally follows paths to their completion (reaching leaves) before backtracking
3. The recursive nature of DFS aligns well with the recursive structure of trees
4. We can easily build the path string as we traverse down and use backtracking to explore alternative paths

The DFS pattern is ideal here as it allows us to:

• Maintain the current path as we traverse
• Detect when we've reached a leaf node
• Backtrack to explore all possible root-to-leaf paths
• Collect all complete paths in our result list

Intuition

When we need to find all paths from root to leaves, we naturally think about exploring the tree systematically. Imagine you're walking through a maze and need to record every possible route from the entrance to any exit. You'd walk down one path, record it when you reach an exit, then backtrack to explore other paths.

The key insight is that we need to:

1. Keep track of our current path as we traverse
2. Know when we've reached a destination (leaf node)
3. Be able to "undo" our steps to explore other paths

This naturally leads us to DFS with backtracking. As we traverse down the tree, we build our path by adding each node's value. When we reach a leaf (a node with no children), we've found a complete path and can save it. Then we need to backtrack - remove the current node from our path - so we can explore other branches.

Think of it like building a string of beads: we add a bead (node value) as we go down, and when we need to try a different path, we remove the last bead and try another direction. The temporary list t acts as our bead string, growing as we go deeper and shrinking as we backtrack.

The beauty of this approach is that the recursive call stack naturally handles the backtracking for us. Each recursive call represents a decision point in the tree, and when a call returns, we automatically return to the previous decision point. By adding t.pop() after the recursive calls, we ensure our path list accurately reflects our current position in the tree traversal.

Solution Approach

The solution implements a DFS traversal with backtracking using a helper function. Let's walk through the implementation step by step:

Core Data Structures:

• ans: A list to store all complete root-to-leaf paths as strings
• t: A temporary list that acts as a stack to build the current path

The DFS Helper Function:

1. Base Case: If the current node is None, we simply return (nothing to process)

2. Path Building: Add the current node's value to our temporary path list t by converting it to a string: t.append(str(root.val))

3. Leaf Detection: Check if the current node is a leaf by verifying both children are None:

   if root.left is None and root.right is None:
       ans.append("->".join(t))

   When we find a leaf, we join all values in t with "->" to create the path string and add it to our answer list

4. Recursive Exploration: If not a leaf, recursively explore both subtrees:

   dfs(root.left)
   dfs(root.right)

5. Backtracking: After exploring both children (or determining it's a leaf), remove the current node's value from the path:

   t.pop()

   This crucial step ensures that when we return to the parent node, our path list t accurately reflects the path up to the parent, allowing us to explore other branches

Main Function Flow:

1. Initialize empty lists for ans (final results) and t (temporary path)
2. Call dfs(root) to start the traversal from the root
3. Return ans containing all root-to-leaf paths

The algorithm visits each node exactly once, making it O(n) in time complexity. The space complexity is O(n) for the recursion stack in the worst case (skewed tree) and for storing the output paths.

Example Walkthrough

Let's walk through a concrete example to understand how the DFS with backtracking solution works.

Consider this binary tree:

       1
      / \
     2   3
      \
       5

We want to find all root-to-leaf paths: ["1->2->5", "1->3"]

Step-by-step execution:

1. Start at root (1)

   • t = []
   • Add 1 to path: t = ["1"]
   • Node 1 has children, so continue exploring

2. Go left to node 2

   • Add 2 to path: t = ["1", "2"]
   • Node 2 has a right child, so continue

3. Go right to node 5

   • Add 5 to path: t = ["1", "2", "5"]
   • Node 5 is a leaf (no children)!
   • Join path with "->": "1->2->5"
   • Add to answer: ans = ["1->2->5"]
   • Backtrack: Remove 5 from path: t = ["1", "2"]

4. Back at node 2

   • Left child is None (already explored)
   • Right child is done (already explored)
   • Backtrack: Remove 2 from path: t = ["1"]

5. Back at root (1), go right to node 3

   • Add 3 to path: t = ["1", "3"]
   • Node 3 is a leaf (no children)!
   • Join path with "->": "1->3"
   • Add to answer: ans = ["1->2->5", "1->3"]
   • Backtrack: Remove 3 from path: t = ["1"]

6. Back at root (1)

   • Both children explored
   • Backtrack: Remove 1 from path: t = []
   • Return ans = ["1->2->5", "1->3"]

The key insight is how the temporary list t grows and shrinks:

• It grows as we traverse down: [] → ["1"] → ["1","2"] → ["1","2","5"]
• It shrinks as we backtrack: ["1","2","5"] → ["1","2"] → ["1"] → ["1","3"] → ["1"] → []

This backtracking mechanism ensures we can explore all paths while maintaining the correct current path at each step of the traversal.

Solution Implementation

Time and Space Complexity

Time Complexity: O(N²) in the worst case, where N is the number of nodes in the binary tree.

• The DFS traversal visits each node exactly once, which takes O(N) time.
• At each leaf node, we create a string by joining the path elements using "->".join(t). In the worst case (a skewed tree), the path length can be O(N), and string concatenation takes O(N) time.
• The number of leaf nodes can be at most O(N) (in the case of a skewed tree, there's only 1 leaf, but in a balanced tree, it could be O(N/2)).
• Therefore, the total time complexity is O(N) for traversal + O(N) for string construction at each leaf node in the worst case = O(N²).

Space Complexity: O(N) in the worst case.

• The recursion stack depth can be at most O(N) in the case of a skewed tree (or O(log N) for a balanced tree).
• The temporary list t stores the current path, which can have at most O(N) elements in the worst case.
• The output list ans stores all root-to-leaf paths. In the worst case (a complete binary tree), there can be O(N/2) leaf nodes, and each path has an average length of O(log N), resulting in O(N log N) total characters stored. However, since we're typically counting space complexity in terms of the number of nodes, this is considered O(N).
• The dominant factor is O(N) for the recursion stack and path storage.

Common Pitfalls

1. Forgetting to Backtrack (Missing pop() operation)

The Pitfall: One of the most common mistakes is forgetting to remove the current node from the path after processing its subtrees. Without the current_path.pop() line, the path list keeps accumulating nodes incorrectly, leading to wrong path representations.

Incorrect Code Example:

def dfs(node):
    if node is None:
        return
  
    current_path.append(str(node.val))
  
    if node.left is None and node.right is None:
        result_paths.append("->".join(current_path))
    else:
        dfs(node.left)
        dfs(node.right)
  
    # MISSING: current_path.pop()  ← This line is crucial!

What Goes Wrong: Without backtracking, if you have a tree like:

      1
     / \
    2   3

After visiting path 1->2, the current_path would still contain [1, 2]. When you then visit node 3, the path becomes [1, 2, 3] instead of [1, 3], resulting in incorrect output: ["1->2", "1->2->3"] instead of ["1->2", "1->3"].

The Solution: Always remember to pop the current node from the path after exploring all its children:

def dfs(node):
    if node is None:
        return
  
    current_path.append(str(node.val))
  
    if node.left is None and node.right is None:
        result_paths.append("->".join(current_path))
    else:
        dfs(node.left)
        dfs(node.right)
  
    current_path.pop()  # ← Critical for backtracking!

2. Creating a New List Instead of Using Backtracking

The Pitfall: Some might try to pass a new copy of the path list to each recursive call instead of using a shared list with backtracking:

def dfs(node, path):
    if node is None:
        return
  
    # Creating a new list for each recursive call
    new_path = path + [str(node.val)]
  
    if node.left is None and node.right is None:
        result_paths.append("->".join(new_path))
    else:
        dfs(node.left, new_path)
        dfs(node.right, new_path)

What Goes Wrong: While this approach works correctly, it's less efficient in terms of space complexity. Creating new lists for each recursive call uses O(n * h) extra space where h is the height of the tree, compared to O(h) for the backtracking approach.

The Solution: Use a single shared path list with proper backtracking for optimal space efficiency. The backtracking approach reuses the same list throughout the traversal, making it more memory-efficient.

3. Not Converting Node Values to Strings

The Pitfall: Forgetting to convert node values to strings before adding them to the path:

current_path.append(node.val)  # Wrong: should be str(node.val)

What Goes Wrong: When you try to join the path with "->".join(current_path), Python will throw a TypeError because join() expects an iterable of strings, not integers.

The Solution: Always convert node values to strings before adding them to the path:

current_path.append(str(node.val))