Bird
Raised Fist0

Identify the line causing incorrect sums on some inputs: ```python def dfs(node, current_sum): if node is None: return 0 current_sum = current_sum * 10 + node.val if node.left is None and node.right is None: return current_sum return dfs(node.left, current_sum) + dfs(node.right, current_sum) ```

medium🐛 Buggy Code Q7 of Q15
Tree: Depth-First Search - Sum Root to Leaf Numbers
Analyze the following recursive DFS code snippet for summing root-to-leaf numbers. Identify the line causing incorrect sums on some inputs: ```python def dfs(node, current_sum): if node is None: return 0 current_sum = current_sum * 10 + node.val if node.left is None and node.right is None: return current_sum return dfs(node.left, current_sum) + dfs(node.right, current_sum) ```
ALine 2: if node is None: return 0
BLine 4: current_sum = current_sum * 10 + node.val
CLine 6: if node.left is None and node.right is None: return current_sum
DLine 7: return dfs(node.left, current_sum) + dfs(node.right, current_sum)
Step-by-Step Solution
Solution:
  1. Step 1: Understand base case

    Returning 0 when node is None causes incorrect addition.
  2. Step 2: Why is this a problem?

    When one child is None, returning 0 adds zero incorrectly to sum.
  3. Step 3: Correct approach

    Return 0 only when both children are None or handle None children separately.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Base case must not add zero for missing child [OK]
Quick Trick: Base case returning 0 adds incorrect sums [OK]
Common Mistakes:
MISTAKES
  • Returning 0 for None nodes adds unwanted zeros
  • Not checking leaf nodes properly
  • Incorrectly accumulating sums in recursion
Trap Explanation:
PITFALL
  • Returning 0 for None nodes incorrectly contributes to sum.
Interviewer Note:
CONTEXT
  • Tests ability to identify subtle bugs in recursive DFS implementations.
Master "Sum Root to Leaf Numbers" 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