[Solved] Consider the following code snippet implementing the optimal DFS approach for the Path... Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? | Tree: Depth-First Search

Tree: Depth-First Search - Path Sum

Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)

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

ATrue

BFalse

CRaises an exception due to null pointer

DReturns True only if the root value equals targetSum

Step-by-Step Solution

Step 1: Trace the path sums
Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.
Step 2: Confirm code logic
The DFS returns True as soon as it finds the matching path sum at a leaf node.
Final Answer:
Option A -> Option A
Quick Check:
Path 5↔4↔11↔2 sums to 22, so return True [OK]

Quick Trick: Check all root-to-leaf paths, not just partial sums [OK]

Common Mistakes:

MISTAKES

Stopping at non-leaf nodes
Ignoring leaf node condition

Trap Explanation:

PITFALL

Some think partial sums at internal nodes suffice, but only leaf paths count.

Interviewer Note:

CONTEXT

Tests ability to mentally execute DFS and understand leaf node checks.

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

Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)?

Step 1: Trace the path sums

Step 2: Confirm code logic

Final Answer:

Quick Check:

Want More Practice?