Problem Description

You are given a binary tree and a target sum. Your task is to find all paths from the root node to any leaf node where the sum of all node values along the path equals the target sum.

Key points to understand:

• A root-to-leaf path starts at the root node and ends at a leaf node (a node with no children)
• You need to return all valid paths, not just count them
• Each path should be represented as a list of node values (not node objects)
• The path sum is calculated by adding up all node values along the path

For example, if you have a binary tree and targetSum = 22, you need to traverse from the root to all leaf nodes, keeping track of the sum along each path. Whenever you reach a leaf node and the accumulated sum equals 22, that path should be included in your answer.

The solution uses Depth-First Search (DFS) with backtracking. It maintains a running sum s and a temporary path list t. As it traverses down the tree, it adds each node's value to both the sum and the path. When reaching a leaf node with the correct sum, it saves a copy of the current path to the answer list. The t.pop() operation at the end implements backtracking - removing the current node from the path before returning to explore other branches.

The algorithm visits each node once, building up paths incrementally and only storing complete valid paths that sum to the target value.

Flowchart Walkthrough

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

Is it a graph?

• Yes: While not explicitly a graph problem, a binary tree is a special type of graph (specifically, a connected acyclic graph).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree, where we need to traverse from root to leaf nodes.

DFS

• Yes: This leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this problem, which makes perfect sense because:

1. We need to explore complete paths from root to leaf (depth-first nature)
2. We need to track the path and sum as we traverse down
3. We need to backtrack when we finish exploring a path to try other branches
4. DFS naturally maintains the path state as we recursively traverse the tree

The DFS approach with backtracking is ideal here since we need to:

• Traverse each complete root-to-leaf path
• Maintain a running sum and current path
• Record valid paths when we reach a leaf with the target sum
• Backtrack (remove nodes from current path) to explore alternative paths

This is exactly what the provided solution implements - using DFS to traverse the tree while maintaining a temporary path list t and running sum s, with backtracking via t.pop() after exploring each subtree.

Intuition

When we need to find all paths from root to leaves with a specific sum, we need to explore every possible path in the tree. This immediately suggests a traversal approach where we visit every node.

The key insight is that we need to track two things as we traverse: the current path we're on and the running sum of that path. Since we're looking for root-to-leaf paths, we must go all the way down to the leaves before making any decisions - this naturally points to a depth-first approach rather than breadth-first.

Think of it like exploring a maze where you need to find all complete paths from entrance to exit that are exactly a certain length. You'd walk down one path completely, keeping track of where you've been and how far you've walked. When you reach a dead end (leaf), you check if your distance matches the target. Then you backtrack to the last junction and try a different path.

The backtracking aspect is crucial here. After we finish exploring one path and record it if valid, we need to "undo" our last step to explore other branches. This is why we use t.append(root.val) when going down and t.pop() when coming back up. The t[:] creates a copy of the current path when we find a valid one, because the original list t will keep changing as we backtrack and explore other paths.

The recursive DFS structure naturally handles this exploration pattern - each recursive call represents going one level deeper in the tree, and when the call returns, we automatically backtrack to the previous level. The base case (reaching a leaf with the target sum) is where we capture our result, and the recursive calls to left and right children ensure we explore all possible paths.

Solution Approach

The solution implements DFS (Depth-First Search) with backtracking to explore all root-to-leaf paths. Let's walk through the implementation step by step:

Data Structures Used:

• ans: A list to store all valid paths that sum to targetSum
• t: A temporary list that maintains the current path being explored
• s: An integer tracking the running sum of the current path

Algorithm Implementation:

1. Initialize the tracking variables: We start with an empty answer list ans and an empty temporary path t. The DFS function is called with the root and initial sum of 0.

2. Base Case: If we reach a None node, we simply return. This handles the case where we've gone beyond a leaf node.

3. Process Current Node:

   • Add the current node's value to the running sum: s += root.val
   • Add the current node's value to the path: t.append(root.val)

4. Check for Valid Path: When we reach a leaf node (both root.left and root.right are None) and the current sum equals targetSum, we've found a valid path. We add a copy of the current path to our answer: ans.append(t[:]). The t[:] creates a shallow copy, which is important because t will be modified as we backtrack.

5. Recursive Exploration:

   • Recursively explore the left subtree: dfs(root.left, s)
   • Recursively explore the right subtree: dfs(root.right, s)
   • Both calls pass the updated sum but use the same path list t

6. Backtracking: After exploring both subtrees, we remove the current node from the path with t.pop(). This is the key backtracking step that allows us to explore other branches with the correct path state.

Why This Works:

• The DFS ensures we explore every root-to-leaf path
• The running sum s is passed by value, so each recursive call has its own sum
• The path list t is shared across all recursive calls, which is why we need explicit backtracking with t.pop()
• By only checking and recording paths at leaf nodes, we ensure we're getting complete root-to-leaf paths

Time Complexity: O(N²) in the worst case, where N is the number of nodes. We visit each node once (O(N)), and in the worst case, we might need to copy O(N) nodes for each leaf path.

Space Complexity: O(N) for the recursion stack and the temporary path storage.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this binary tree with targetSum = 7:

      3
     / \
    1   4
   /   / \
  3   2   1

Step-by-step execution:

1. Start at root (3)

   • s = 0 + 3 = 3
   • t = [3]
   • Not a leaf, continue exploring

2. Go left to node (1)

   • s = 3 + 1 = 4
   • t = [3, 1]
   • Not a leaf, continue exploring

3. Go left to node (3)

   • s = 4 + 3 = 7
   • t = [3, 1, 3]
   • This is a leaf! Check: s == 7 ✓
   • Add [3, 1, 3] to answer
   • Backtrack: t.pop() → t = [3, 1]

4. Back at node (1), right child is None

   • Backtrack: t.pop() → t = [3]

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

   • s = 3 + 4 = 7
   • t = [3, 4]
   • Not a leaf, continue exploring

6. Go left to node (2)

   • s = 7 + 2 = 9
   • t = [3, 4, 2]
   • This is a leaf! Check: s == 7 ✗ (s = 9)
   • Backtrack: t.pop() → t = [3, 4]

7. Back at node (4), go right to node (1)

   • s = 7 + 1 = 8
   • t = [3, 4, 1]
   • This is a leaf! Check: s == 7 ✗ (s = 8)
   • Backtrack: t.pop() → t = [3, 4]

8. Finished exploring, backtrack from node (4)

   • t.pop() → t = [3]

Final Result: [[3, 1, 3]]

The key points illustrated:

• We maintain a running path t that grows as we go deeper
• We calculate the sum incrementally as we traverse
• We only record paths when reaching leaves with the correct sum
• Backtracking (t.pop()) allows us to reuse the same list for exploring different branches
• The path is copied (t[:]) when adding to the answer to preserve the current state

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) where n is the number of nodes in the binary tree.

The algorithm performs a depth-first search (DFS) traversal visiting each node exactly once, which takes O(n) time. However, at each leaf node where the path sum equals the target, we create a copy of the current path using t[:]. In the worst case, the tree could be a complete binary tree where every root-to-leaf path has the same sum as the target. For a complete binary tree with n nodes, there are approximately n/2 leaf nodes, and the height is O(log n). Each path copy operation takes O(log n) time since that's the length of the path. Therefore, the worst-case time complexity is O(n) for traversal plus O((n/2) * log n) for copying paths, which simplifies to O(n log n).

However, considering a skewed tree (like a linked list) where all nodes form a single path, if this path sums to the target, copying this path would take O(n) time. With only one such path, the total time would be O(n). But in a more pathological case where we need to consider all possible paths and their prefixes in certain tree configurations, the time complexity can reach O(n²).

Space Complexity: O(n)

The space complexity consists of:

• The recursion call stack, which in the worst case (skewed tree) can go as deep as O(n)
• The temporary path list t which stores at most O(n) elements in the worst case (skewed tree)
• The output list ans which stores all valid paths, but this is not counted as auxiliary space since it's part of the required output

Therefore, the overall space complexity is O(n).

Common Pitfalls

1. Forgetting to Create a Copy of the Path

One of the most common mistakes is adding the current path directly to the result list without creating a copy:

Incorrect Code:

if node.left is None and node.right is None and current_sum == targetSum:
    result.append(current_path)  # WRONG! This adds a reference, not a copy

Why This Fails: Since current_path is a mutable list that gets modified during backtracking, all references in result will point to the same list object. After the DFS completes, result will contain multiple references to an empty list.

Correct Solution:

if node.left is None and node.right is None and current_sum == targetSum:
    result.append(current_path[:])  # Creates a shallow copy
    # Or alternatively: result.append(list(current_path))

2. Incorrect Leaf Node Detection

Another frequent error is incorrectly identifying leaf nodes by checking only one child:

Incorrect Code:

# Wrong: This might include paths to internal nodes
if node.left is None or node.right is None:  # WRONG! Uses OR instead of AND
    if current_sum == targetSum:
        result.append(current_path[:])

Why This Fails: A node with only one child is not a leaf node. Using OR would incorrectly include paths that end at internal nodes with one child.

Correct Solution:

# A leaf node has no children (both left and right are None)
if node.left is None and node.right is None:
    if current_sum == targetSum:
        result.append(current_path[:])

3. Forgetting to Backtrack

Missing the backtracking step will cause the path to accumulate nodes incorrectly:

Incorrect Code:

def dfs(node, current_sum):
    if node is None:
        return
  
    current_sum += node.val
    current_path.append(node.val)
  
    if node.left is None and node.right is None and current_sum == targetSum:
        result.append(current_path[:])
  
    dfs(node.left, current_sum)
    dfs(node.right, current_sum)
    # MISSING: current_path.pop()  # Forgot to backtrack!

Why This Fails: Without removing the current node from the path after exploring its subtrees, the path will incorrectly contain nodes from previously explored branches, leading to wrong paths in the result.

Correct Solution: Always include the backtracking step after recursive calls:

dfs(node.left, current_sum)
dfs(node.right, current_sum)
current_path.pop()  # Essential backtracking step

4. Modifying the Sum Variable Incorrectly

Using the augmented assignment operator for the sum in the wrong scope:

Incorrect Code:

def dfs(node):
    if node is None:
        return
  
    nonlocal current_sum  # If current_sum is defined outside
    current_sum += node.val  # WRONG! Modifies the shared sum
    current_path.append(node.val)
  
    # ... rest of the code
  
    current_sum -= node.val  # Need to manually restore

Why This Fails: If current_sum is a shared variable, modifying it directly requires manual restoration, making the code error-prone and harder to maintain.

Correct Solution: Pass the sum as a parameter to create separate sum values for each recursive branch:

def dfs(node, current_sum):  # Pass sum as parameter
    if node is None:
        return
  
    current_sum += node.val  # Creates a new local sum
    # No need to restore since each call has its own sum