LeetCode 113: Path Sum II Solution in Python Explained

Problem Statement

In LeetCode 113, you’re given the root of a binary tree and an integer targetSum. Your task is to return a list of lists, where each inner list represents a root-to-leaf path (a leaf has no children) with node values summing to targetSum. This extends LeetCode 112: Path Sum, which checks for existence, to finding all such paths, and differs from minimum depth like LeetCode 111: Minimum Depth of Binary Tree.

Constraints

• Number of nodes: 0 <= n <= 5000
• Node values: -1000 <= Node.val <= 1000
• Target sum: -1000 <= targetSum <= 1000

Example

Let’s see some cases:

Copy codeInput: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: Paths: 5->4->11->2 (22), 5->8->4->5 (22).

Copy codeInput: root = [1,2,3], targetSum = 5
      1
     / \
    2   3
Output: []
Explanation: Paths: 1->2 (3), 1->3 (4), none equal 5.

Copy codeInput: root = [], targetSum = 0
Output: []
Explanation: Empty tree, no paths.

These examples show we’re collecting all target-sum paths.

Understanding the Problem

How do you solve LeetCode 113: Path Sum II in Python? Take root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22. We need all root-to-leaf paths summing to 22—paths [5,4,11,2] (5+4+11+2=22) and [5,8,4,5] (5+8+4+5=22), so return [[5,4,11,2],[5,8,4,5]]. For [1,2,3], targetSum = 5, no paths match (1+2=3, 1+3=4), so []. This isn’t a balance check like LeetCode 110: Balanced Binary Tree; it’s about finding all paths with a specific sum. We’ll use: 1. Recursive DFS with Path Tracking: O(n) time, O(h) space—our best solution. 2. Stack-Based DFS with Path Tracking: O(n) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive DFS with Path Tracking Approach

Explanation

Recursive DFS with Path Tracking explores all root-to-leaf paths by recursively subtracting each node’s value from targetSum, tracking the current path in a list, and adding it to the result when a leaf matches the remaining sum. It uses backtracking to remove nodes after exploration. This is the best solution due to its O(n) time complexity, simplicity, and efficient use of recursion to build paths without excessive memory, making it ideal for collecting all matching paths.

For [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22:

• Path [5]: 22 - 5 = 17.
• [5,4]: 17 - 4 = 13, [5,4,11]: 13 - 11 = 2, [5,4,11,2]: 2 - 2 = 0, add path.
• [5,8]: 17 - 8 = 9, [5,8,4]: 9 - 4 = 5, [5,8,4,5]: 5 - 5 = 0, add path.
• Result: [[5,4,11,2],[5,8,4,5]].

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Goal: Return [[5,4,11,2],[5,8,4,5]].

• Start: pathSum(5, 22, [], []).
• Step 1: root = 5, path = [5], remain = 22 - 5 = 17.
• Left: pathSum(4, 17, [5], []).
• root = 4, path = [5,4], remain = 17 - 4 = 13.
• Left: pathSum(11, 13, [5,4], []).
• root = 11, path = [5,4,11], remain = 13 - 11 = 2.
• Left: pathSum(7, 2, [5,4,11], []).
• Leaf 7, remain = 2 - 7 = -5, no match.
• Right: pathSum(2, 2, [5,4,11], []).
• Leaf 2, remain = 2 - 2 = 0, add [5,4,11,2].
• Backtrack, path = [5,4].
• Backtrack, path = [5].
• Right: pathSum(8, 17, [5], [[5,4,11,2]]).
• root = 8, path = [5,8], remain = 17 - 8 = 9.
• Left: pathSum(13, 9, [5,8], [[5,4,11,2]]).
• Leaf 13, remain = 9 - 13 = -4, no match.
• Right: pathSum(4, 9, [5,8], [[5,4,11,2]]).
• root = 4, path = [5,8,4], remain = 9 - 4 = 5.
• Left: pathSum(5, 5, [5,8,4], [[5,4,11,2]]).
• Leaf 5, remain = 5 - 5 = 0, add [5,8,4,5].
• Right: pathSum(1, 5, [5,8,4], [[5,4,11,2],[5,8,4,5]]).
• Leaf 1, remain = 5 - 1 = 4, no match.
• Finish: Return [[5,4,11,2],[5,8,4,5]].

Example 2: root = [1,2,3], targetSum = 5

Goal: Return [].

• Start: pathSum(1, 5, [], []).
• Step 1: root = 1, path = [1], remain = 5 - 1 = 4.
• Left: pathSum(2, 4, [1], []).
• Leaf 2, remain = 4 - 2 = 2, no match.
• Right: pathSum(3, 4, [1], []).
• Leaf 3, remain = 4 - 3 = 1, no match.
• Finish: Return [].

Example 3: root = [], targetSum = 0

Goal: Return [].

• Start: pathSum(None, 0, [], []).
• Step 1: Null root, return empty list.
• Finish: Return [].

How the Code Works (Recursive DFS with Path Tracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass 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]]:
    # Line 1: Initialize result list
    result = []
    # Stores all valid paths (e.g., initially [])

    # Line 2: Define recursive helper function
    def dfs(node: TreeNode, remaining: int, path: list[int]):
        # node = current node (e.g., 5), remaining = target sum left, path = current path

        # Line 3: Base case - check if node is null
        if not node:
            # If node is None (e.g., empty tree or beyond leaf), return
            return

        # Line 4: Add current node to path
        path.append(node.val)
        # Tracks current path (e.g., [5] → [5,4])

        # Line 5: Check if leaf node
        if not node.left and not node.right:
            # If leaf (e.g., 2), check remaining sum
            if remaining == node.val:
                # If remaining matches node value (e.g., 2 = 2), add path
                result.append(path[:])
                # Copy path to result (e.g., [5,4,11,2])
            # Backtrack happens after return

        # Line 6: Recursively explore left subtree
        if node.left:
            dfs(node.left, remaining - node.val, path)
            # Subtracts current value (e.g., 17 - 4 = 13 for 4)

        # Line 7: Recursively explore right subtree
        if node.right:
            dfs(node.right, remaining - node.val, path)
            # Subtracts current value (e.g., 17 - 8 = 9 for 8)

        # Line 8: Backtrack by removing current node
        path.pop()
        # Removes node after exploration (e.g., [5,4,11,2] → [5,4,11])

    # Line 9: Start DFS from root
    dfs(root, targetSum, [])
    # Initiates with root, full target, empty path (e.g., 5, 22, [])

    # Line 10: Return all valid paths
    return result
    # Returns final list (e.g., [[5,4,11,2],[5,8,4,5]])

This detailed breakdown clarifies how recursive DFS with path tracking efficiently collects all target-sum paths.

Alternative: Stack-Based DFS with Path Tracking Approach

Explanation

Stack-Based DFS with Path Tracking uses a stack to iteratively explore paths, storing each node, remaining sum, and current path. It adds paths to the result when a leaf matches the target sum. This is a practical alternative, avoiding recursion while maintaining O(n) time, useful for managing stack depth explicitly.

For [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22:

• Stack: [(5,22,[])], [(4,17,[5]),(8,17,[5])], etc.
• Leaf 2: 0 matches, add [5,4,11,2].
• Leaf 5: 0 matches, add [5,8,4,5].

Step-by-Step Example (Alternative)

For [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22:

• Start: stack = [(5, 22, [])].
• Step 1: Pop (5,22,[]), push (4,17,[5]), (8,17,[5]).
• Step 2: Pop (8,17,[5]), push (13,9,[5,8]), (4,9,[5,8]).
• Step 3: Pop (4,9,[5,8]), push (5,5,[5,8,4]), (1,5,[5,8,4]).
• Step 4: Pop (1,5,[5,8,4]), no match.
• Step 5: Pop (5,5,[5,8,4]), leaf, matches, add [5,8,4,5].
• Step 6: Continue, pop (4,17,[5]), push (11,13,[5,4]).
• Step 7: Pop (11,13,[5,4]), push (7,2,[5,4,11]), (2,2,[5,4,11]).
• Step 8: Pop (2,2,[5,4,11]), leaf, matches, add [5,4,11,2].
• Finish: Return [[5,4,11,2],[5,8,4,5]].

How the Code Works (Stack-Based DFS)

Copy codedef pathSumStack(root: TreeNode, targetSum: int) -> list[list[int]]:
    if not root:
        return []
    stack = [(root, targetSum, [])]
    result = []
    while stack:
        node, remaining, path = stack.pop()
        path = path + [node.val]
        if not node.left and not node.right and remaining == node.val:
            result.append(path)
        if node.right:
            stack.append((node.right, remaining - node.val, path))
        if node.left:
            stack.append((node.left, remaining - node.val, path))
    return result

Complexity

• Recursive DFS with Path Tracking:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Stack-Based DFS with Path Tracking:
• Time: O(n) – visits each node once.
• Space: O(h) – stack size.

Efficiency Notes

Recursive DFS with Path Tracking is the best solution with O(n) time and O(h) space, offering simplicity and efficiency—Stack-Based DFS matches complexity, providing an iterative alternative that’s robust for deep trees, though slightly more complex to manage paths.

Key Insights

• Path Tracking: Build paths dynamically.
• DFS: Explores all root-to-leaf paths.
• Leaf Match: Remaining sum = 0.

Additional Example

For root = [1,2,3], targetSum = 4:

• Goal: [[1,3]].
• DFS: 1->3 = 4, add [1,3].

Edge Cases

• Empty Tree: [] → [].
• Single Node: [5], targetSum = 5 → [[5]].
• Unbalanced: [1,2,null,3], targetSum = 4 → [[1,3]].

Both solutions handle these well.

Final Thoughts

LeetCode 113: Path Sum II in Python is a rewarding path-finding challenge. The Recursive DFS with Path Tracking solution stands out for its efficiency and elegance, while Stack-Based DFS with Path Tracking offers an iterative approach. Want more? Try LeetCode 112: Path Sum for existence checks or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 113 on LeetCode with [5,4,8,11,null,13,4,7,2,null,null,5,1] and targetSum = 22, aiming for [[5,4,11,2],[5,8,4,5]]—test your skills now!