LeetCode 112: Path Sum Solution in Python Explained

Problem Statement

In LeetCode 112, you’re given the root of a binary tree and an integer targetSum. Your task is to return true if there’s a path from the root to a leaf node (no children) where the sum of node values equals targetSum, or false if no such path exists. This contrasts with minimum depth like LeetCode 111: Minimum Depth of Binary Tree, focusing on path sums rather than path lengths.

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,null,1], targetSum = 22
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
Output: true
Explanation: Path 5->4->11->2 sums to 22.

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

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

These examples show we’re searching for a target-sum path.

Understanding the Problem

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

Let’s dive into the best solution.

Best Solution: Recursive DFS Approach

Explanation

Recursive DFS explores all root-to-leaf paths by recursively subtracting each node’s value from targetSum, checking if the remaining sum equals 0 at a leaf. It returns true if any path satisfies this condition. This is the best solution due to its O(n) time complexity, simplicity, and efficient use of recursion to track sums without extra data structures, making it ideal for path sum problems.

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

• Start: 22 - 5 = 17.
• Left: 17 - 4 = 13, 13 - 11 = 2, 2 - 2 = 0 (leaf), true.
• Right paths don’t match, but one true path suffices.

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,null,1], targetSum = 22

Goal: Return true.

• Start: hasPathSum(5, 22).
• Step 1: root = 5, remain = 22 - 5 = 17.
• Left: hasPathSum(4, 17).
• root = 4, remain = 17 - 4 = 13.
• Left: hasPathSum(11, 13).
• root = 11, remain = 13 - 11 = 2.
• Left: hasPathSum(7, 2) → 2 - 7 = -5, false.
• Right: hasPathSum(2, 2) → 2 - 2 = 0, leaf, true.
• Return true (one path works).
• Return true.
• Right: Not needed, one true path suffices.
• Finish: Return true.

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

Goal: Return false.

• Start: hasPathSum(1, 5).
• Step 1: root = 1, remain = 5 - 1 = 4.
• Left: hasPathSum(2, 4) → 4 - 2 = 2, leaf, false.
• Right: hasPathSum(3, 4) → 4 - 3 = 1, leaf, false.
• Finish: Return false.

Example 3: root = []

Goal: Return false.

• Start: hasPathSum(None, 0).
• Step 1: Null root, return false.
• Finish: Return false.

How the Code Works (Recursive DFS) – 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 hasPathSum(root: TreeNode, targetSum: int) -> bool:
    # Line 1: Base case - check if root is null
    if not root:
        # If root is None (e.g., empty tree), no path exists
        return False

    # Line 2: Update remaining sum
    remaining = targetSum - root.val
    # Subtracts current value (e.g., 22 - 5 = 17)

    # Line 3: Check if leaf node
    if not root.left and not root.right:
        # If no children (e.g., leaf like 2), check if remaining sum is 0
        return remaining == 0
        # e.g., remaining=0 for 2, true; remaining=2 for 3, false

    # Line 4: Recursively check left subtree
    left_path = hasPathSum(root.left, remaining) if root.left else False
    # Explores left child (e.g., 4 with 17), false if no left
    # Returns true if path found, false otherwise

    # Line 5: Recursively check right subtree
    right_path = hasPathSum(root.right, remaining) if root.right else False
    # Explores right child (e.g., 8 with 17), false if no right
    # Returns true if path found, false otherwise

    # Line 6: Return if any path matches
    return left_path or right_path
    # True if either subtree has a valid path (e.g., true from 5->4->11->2)
    # False if no path matches

This detailed breakdown clarifies how recursive DFS efficiently finds a target-sum path.

Alternative: Stack-Based DFS Approach

Explanation

Stack-Based DFS uses a stack to iteratively explore paths, tracking the current node and remaining sum. It checks each leaf for a match with targetSum. This is a practical alternative, avoiding recursion while maintaining O(n) time, suitable when recursion depth is a concern.

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

• Stack: [(5,22)], [(4,17),(8,17)], [(11,13),(8,17)], [(7,2),(2,2),(8,17)].
• Leaf 2: 0 matches, true.

Step-by-Step Example (Alternative)

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

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

How the Code Works (Stack-Based DFS)

Copy codedef hasPathSumStack(root: TreeNode, targetSum: int) -> bool:
    if not root:
        return False
    stack = [(root, targetSum)]
    while stack:
        node, remaining = stack.pop()
        if not node.left and not node.right and remaining == node.val:
            return True
        if node.right:
            stack.append((node.right, remaining - node.val))
        if node.left:
            stack.append((node.left, remaining - node.val))
    return False

Complexity

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

Efficiency Notes

Recursive DFS 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 useful for avoiding recursion limits, though slightly more complex to implement.

Key Insights

• Path Sum: Root-to-leaf total.
• DFS: Explores all paths.
• Leaf Check: Remaining sum = 0.

Additional Example

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

• Goal: true.
• DFS: 1->2->3 = 4, true.

Edge Cases

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

Both solutions handle these well.

Final Thoughts

LeetCode 112: Path Sum in Python is a classic path-finding challenge. The Recursive DFS solution excels with its efficiency and clarity, while Stack-Based DFS offers an iterative approach. Want more? Try LeetCode 104: Maximum Depth of Binary Tree for depth basics or LeetCode 94: Binary Tree Inorder Traversal for traversal skills. Ready to practice? Solve LeetCode 112 on LeetCode with [5,4,8,11,null,13,4,7,2,null,null,null,1] and targetSum = 22, aiming for true—test your skills now!