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:
- Empty Input: If
rootisNone, there are no paths; return an empty list immediately. - 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.
- Negative Values: Node values and
targetSumcan 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. - 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.
- Enter node: Append value to path, decrement remaining target sum.
- 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. - Recurse Left/Right.
- 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
- Initialize
resultas an empty list and define a recursive helper function (or use nested closure). - Define base cases: If node is null, return immediately.
- 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_sumand compare against originaltargetSum. 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
resultandpath, updating them in place for efficiency (standard LeetCode pattern).
- Decision: Use nested function with closure over
- Leaf Check: If node has no left/right children, check if the sum of values currently in
pathequalstargetSum. Note: Since we are modifying a list, checking length or using accumulated variable is better than re-summing every time. I will passcurrent_sumto avoid O(N) summation at each step. - Recursive Step: Call helper on left child and right child if they exist.
- 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: where 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
resulthappens 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: . - Space:
- Recursion Stack: where is the height of the tree (worst case , best case ).
- Auxiliary Space: We use a single
pathlist that grows to depth . The result storage depends on output size. - Overall auxiliary space complexity excluding output is .
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 nodecheck 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