[Solved] Examine the following buggy code for the Path Sum problem. Which line contains the subtle bug that causes... Which line contains the subtle bug that causes incorrect results on some inputs? | Tree: Depth-First Search

Tree: Depth-First Search - Path Sum

Examine the following buggy code for the Path Sum problem. Which line contains the subtle bug that causes incorrect results on some inputs?

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if curr_sum == targetSum:  # Bug here
            return True
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

ALine 3: if not node: return False

BLine 6: if curr_sum == targetSum:

CLine 8: return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

DLine 5: curr_sum += node.val

Step-by-Step Solution

Step 1: Understand leaf node condition
The sum should be checked only at leaf nodes, not at every node.
Step 2: Identify the bug
Line 6 checks sum at any node, causing premature True returns for partial paths.
Final Answer:
Option B -> Option B
Quick Check:
Bug causes incorrect True if partial path sum equals targetSum [OK]

Quick Trick: Sum check must be at leaf nodes only [OK]

Common Mistakes:

MISTAKES

Checking sum at internal nodes
Not handling null root

Trap Explanation:

PITFALL

Checking sum too early looks correct but breaks correctness on partial paths.

Interviewer Note:

CONTEXT

Tests ability to spot subtle logic errors in recursion base cases.

Master "Path Sum" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Tree: Depth-First Search Quizzes

Examine the following buggy code for the Path Sum problem. Which line contains the subtle bug that causes incorrect results on some inputs?

Step 1: Understand leaf node condition

Step 2: Identify the bug

Final Answer:

Quick Check:

Want More Practice?