[Solved] Consider the following Python function intended to check if a binary tree has a root-to-leaf path with sum equal to targetSum.... | Tree: Depth-First Search

Tree: Depth-First Search - Path Sum

Consider the following Python function intended to check if a binary tree has a root-to-leaf path with sum equal to targetSum. Identify the logical error in the code snippet below:

def hasPathSum(root, targetSum):
    if root is None:
        return False
    if root.left is None and root.right is None:
        return root.val == targetSum
    return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)

Which statement best describes the issue?

A

The base case incorrectly checks leaf nodes; it should verify if <code>root.val == targetSum</code> only when both children are None.

BThe function does not handle the case when <code>root</code> is None, leading to runtime errors.

CThe recursive calls subtract <code>root.val</code> from <code>targetSum</code> incorrectly; it should add instead.

DThe function should return True immediately when <code>root.val == targetSum</code>, regardless of leaf status.

Step-by-Step Solution

Solution:

Step 1: Understand the base case
The base case checks if the current node is a leaf (both children None) and compares root.val to targetSum.
Step 2: Verify correctness
This is the correct approach because only root-to-leaf paths count. The function returns True if the leaf's value equals the remaining sum.
Step 3: Identify the error
Actually, the code snippet is correct in this regard; thus, the error is not in the base case but elsewhere.
Step 4: Re-examine options
The base case incorrectly checks leaf nodes; it should verify if root.val == targetSum only when both children are None. states the base case is incorrect, but it is correct. The function does not handle the case when root is None, leading to runtime errors. is false because the function handles root is None. The recursive calls subtract root.val from targetSum incorrectly; it should add instead. is wrong because subtracting root.val is the correct approach. The function should return True immediately when root.val == targetSum, regardless of leaf status. is incorrect because non-leaf nodes matching targetSum do not guarantee a valid path.
Final Answer:
Option A -> Option A
Quick Check:
Base case must check leaf nodes only [OK]

Quick Trick: Check base case only at leaf nodes [OK]

Common Mistakes:

MISTAKES

Checking targetSum at non-leaf nodes
Not subtracting node value from targetSum
Ignoring null root condition

Trap Explanation:

PITFALL

Option A looks like an error but the base case is correctly implemented for leaf nodes.

Interviewer Note:

CONTEXT

Tests understanding of base case logic in recursive path sum solutions.

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

Consider the following Python function intended to check if a binary tree has a root-to-leaf path with sum equal to targetSum. Identify the logical error in the code snippet below:

Step 1: Understand the base case

Step 2: Verify correctness

Step 3: Identify the error

Step 4: Re-examine options

Final Answer:

Quick Check:

Want More Practice?