Domain 2MediumCORE

Path Sum II

We are given a binary tree and an integer targetSum. The goal is to find all paths from the root to any leaf node where the sum of node values along that path equals targetSum.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Depth-first Search

113. Path Sum II

Model: qwen3.5:9b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 49.5%


Problem Breakdown

We are given a binary tree and an integer targetSum. The goal is to find all paths from the root to any leaf node where the sum of node values along that path equals targetSum.

Inputs:

  • A pointer/reference to the root of a Binary Tree.
  • An integer targetSum.

Outputs:

  • A list of lists, where each inner list represents one valid path (sequence of integers).

Implicit Constraints & Edge Cases:

  1. Empty Input: If root is None, there are no paths; return an empty list immediately.
  2. Leaf Definition: Only nodes with no children count as leaves. A node might be a leaf even if it’s the only child in some skewed structures, but strictly defined here: both left and right must be null.
  3. Negative Values: Node values and targetSum can be negative (range -1000 to 1000). This means we cannot prune branches based on “sum exceeded target” because adding a negative number could bring the sum back down to match later in the tree. We must traverse all valid paths.
  4. Multiple Paths: The same value can appear multiple times; distinct path sequences are required, not just unique sums.

Intuition

This is fundamentally an exploration problem on a graph (the tree). Since we need information from root to leaf and decisions at each node depend on the accumulated sum so far, Depth-First Search (DFS) is the natural choice.

A naive brute-force approach would be: traverse every path, calculate total sum upon reaching a leaf, store if it matches target. This works but requires managing state carefully.

Why not BFS? While possible with queues and storing paths in memory at each level, DFS uses less auxiliary space for stack depth (O(H) vs O(N)) because we only need to hold the current path being explored, whereas a full-level traversal might require holding many partial paths simultaneously if using an iterative queue approach.

Key Insight: We can use Backtracking. Instead of creating new lists at every recursive call (which is expensive in Python), we maintain one mutable list representing current_path.

  1. Enter node: Append value to path, decrement remaining target sum.
  2. Check Leaf Condition: If current node has no children and the accumulated sum matches exactly what’s left of the target? Actually, simpler logic: check if it is a leaf and total sum equals targetSum.
  3. Recurse Left/Right.
  4. Backtrack (Exit): Remove value from path before returning to explore other branches or finish recursion.

This ensures we only store valid paths in our final result list when the condition is met, keeping memory usage proportional to the depth of the tree rather than all intermediate nodes during traversal.

Approach

  1. Initialize result as an empty list and define a recursive helper function (or use nested closure).
  2. Define base cases: If node is null, return immediately.
  3. Update state: Add current node’s value to our tracking path; subtract from remaining target sum for easier comparison at the leaf check. Alternatively, track current_sum and compare against original targetSum. I will use a helper that tracks (node, current_path) but since Python lists are mutable references, we pass one list down or manage it via backtracking logic on an outer scope variable to minimize arguments.
    • Decision: Use nested function with closure over result and path, updating them in place for efficiency (standard LeetCode pattern).
  4. Leaf Check: If node has no left/right children, check if the sum of values currently in path equals targetSum. Note: Since we are modifying a list, checking length or using accumulated variable is better than re-summing every time. I will pass current_sum to avoid O(N) summation at each step.
  5. Recursive Step: Call helper on left child and right child if they exist.
  6. Backtrack: After returning from children calls, pop the current node’s value from path. This ensures that when we return up the stack, the path list is clean for other branches or subsequent recursion levels.

Complexity Analysis

  • Time: O(N)O(N) where NN is the number of nodes in the tree. We visit every node exactly once during traversal (DFS). The cost to copy a valid path into result happens only when we find a solution, so it’s proportional to output size. In worst-case scenarios with many solutions, this dominates, but standard analysis considers input traversal dominant: O(N)O(N).
  • Space:
    • Recursion Stack: O(H)O(H) where HH is the height of the tree (worst case NN, best case log⁡N\log N).
    • Auxiliary Space: We use a single path list that grows to depth HH. The result storage depends on output size.
    • Overall auxiliary space complexity excluding output is O(H)O(H).

Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pathSum(root: 'TreeNode', targetSum: int) -> list[list[int]]:
    result = []
    
    # Helper function for DFS traversal with backtracking
    def dfs(node, current_sum, remaining_target):
        if not node:
            return
        
        # Update the running sum and check leaf condition immediately? 
        # Actually simpler to pass original target or track difference.
        # Let's stick to tracking 'remaining' to avoid re-summing logic errors.
        
        new_remaining = remaining_target - node.val
        
        # Check if this is a leaf node (no children)
        if not node.left and not node.right:
            if new_remaining == 0:
                result.append([node.val]) 
            return

        # Recurse left/right with updated path logic? 
        # Wait, passing 'path' list by reference requires popping.
        # Let's refactor for clarity on backtracking state management.
        
    # Refactored approach using explicit mutable path and remaining sum tracking
    
    def backtrack(node, current_sum):
        if not node:
            return
        
        new_current = current_sum + node.val
        
        # Check leaf condition first to avoid unnecessary recursion or appending invalid paths
        is_leaf = (not node.left) and (not node.right)
        
        if is_leaf:
            if new_current == targetSum:
                result.append([node.val]) 
            return

        # Recurse on children. Note: We don't need to pop here because we are building the path list differently?
        # Standard Backtracking Pattern for Path Sum II usually involves appending and popping a specific 'path' variable.
        
    # Let's implement the standard clean backtracking pattern used in interviews
    
    def solve(node, current_path):
        if not node:
            return
        
        current_path.append(node.val)
        
        is_leaf = (not node.left) and (not node.right)
        
        if is_leaf:
            # Check sum of path against targetSum. 
            # Note: We need to re-sum or track accumulated sum separately? 
            # Re-summing O(depth). Better to pass current_sum in recursion args for efficiency, but Python lists are mutable.
            # Let's use a closure variable 'current_path' and check len(path) == 1 if leaf? No, path has multiple nodes.
            # To avoid re-summation cost inside the loop (though depth is small), let's track sum in recursion args or just accept O(depth). 
            # Given constraints N=5000, O(N^2) worst case for output construction is acceptable if valid paths are few.
            
        backtrack(node.left, current_path.copy()) # This creates new list every time -> inefficient memory?
        
    # Re-evaluating the most efficient Pythonic way: 
    # Pass 'path' by reference and pop() after recursion returns (Backtracking).
    
    def dfs_backtrack(node):
        if not node: return
        
        path.append(node.val)
        
        is_leaf = not node.left and not node.right
        
        if is_leaf:
            if sum(path) == targetSum: # O(depth), acceptable for leaf check only. 
                result.append(list(path)) # Copy to avoid reference issues in outer scope? No, we are popping below.
            
        dfs_backtrack(node.left)
        dfs_backtrack(node.right)
        
        path.pop() # Backtrack
        
    if root:
        solve(root)

# Let's write the final clean implementation logic inside Solution block properly.

Edge Cases Handled

  • Empty Tree: The if not node check handles this immediately, returning an empty list from initialization.
  • Leaf Node Sum Match: If a single-node tree has value equal to targetSum, it is correctly identified as a leaf and added to results.
  • Negative Sums: Since we only prune at the end (leaf) or rely on exact match sum(path) == target, negative values are handled naturally without incorrect pruning logic.
  • Path Copying: We append [node.val] directly when found, but since we use a mutable list for traversal and pop backtracking, any path added to results must be copied (e.g., list(path) or appending the specific value at leaf) because modifying the shared reference after adding would corrupt previous valid paths if not careful. In my logic above: result.append(list(path)) ensures we store a snapshot of that specific valid state before backtracking pops it later? Actually, standard pattern is append to result before popping or copy immediately upon finding match. I will ensure the code copies the list when adding to results.
class Solution:
    def pathSum(self, root: 'TreeNode', targetSum: int) -> List[List[int]]:
        self.result = []
        
        # Helper function for DFS traversal with backtracking
        def dfs(node):
            if not node:
                return
            
            # Add current node to the path
            self.path.append(node.val)
            
            # Check leaf condition (no children)
            is_leaf = not node.left and not node.right
            
            if is_leaf:
                # If sum of path equals targetSum, add a copy to results
                if sum(self.path) == targetSum:
                    self.result.append(list(self.path))
            
            # Recurse on left and right children
            dfs(node.left)
            dfs(node.right)
            
            # Backtrack: remove current node from path before returning up the stack
            self.path.pop()

        if root is not None:
            self.path = []  # Initialize empty list for backtracking
            dfs(root)
        
        return self.result