Bird
Raised Fist0

Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?

easy🧾 Code Trace Q12 of Q15
Tree: Depth-First Search - Path Sum III (Any Path)
Consider the following iterative DFS code snippet for counting paths with sum equal to targetSum in a binary tree. Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?
class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result
A1
B0
C3
D2
Step-by-Step Solution
Solution:
  1. Step 1: Trace initial stack and prefix_counts

    Start with stack=[(1,0,False)], prefix_counts={0:1}, result=0.
  2. Step 2: Process nodes and update result

    Paths summing to 3 are: (1->2) and (3) alone, total 2 paths counted.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two valid paths found matching target sum [OK]
Quick Trick: Count paths by prefix sums during DFS traversal [OK]
Common Mistakes:
MISTAKES
  • Missing the single node path (3)
  • Double counting paths due to prefix_counts not decremented
  • Off-by-one in updating result
Trap Explanation:
PITFALL
  • Candidates often miss that single nodes can form valid paths or forget to decrement prefix_counts on backtrack.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute iterative DFS with prefix sums and track state correctly.
Master "Path Sum III (Any Path)" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes