Bird
Raised Fist0

Consider this iterative postorder traversal code snippet: ```python def postorderTraversal(root): result = [] stack = [] current = root while current or stack: while current: stack.append(current) current = current.left node = stack.pop() result.append(node.val) current = node.right return result ``` What is the subtle bug in this code?

medium🐞 Bug Identification Q7 of Q15
Tree: Depth-First Search - Binary Tree Postorder Traversal
Consider this iterative postorder traversal code snippet: ```python def postorderTraversal(root): result = [] stack = [] current = root while current or stack: while current: stack.append(current) current = current.left node = stack.pop() result.append(node.val) current = node.right return result ``` What is the subtle bug in this code?
AStack is emptied too early causing missing nodes
BNot checking if root is None causes runtime error
CAppending node value before traversing right subtree causes incorrect order
DUsing 'current = node.right' instead of 'current = None' causes infinite loop
Step-by-Step Solution
Solution:
  1. Step 1: Analyze order of appending node values

    Appending node before right subtree traversal outputs preorder-like order, not postorder.
  2. Step 2: Identify correct traversal order

    Postorder requires visiting left, right, then node; this code appends node too early.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Output order is incorrect due to premature append [OK]
Quick Trick: Append after right subtree traversal for postorder [OK]
Common Mistakes:
MISTAKES
  • Appending node before right child
  • Ignoring last visited node tracking
Trap Explanation:
PITFALL
  • Candidates often miss that appending before right subtree traversal breaks postorder order.
Interviewer Note:
CONTEXT
  • Tests ability to spot subtle traversal order bugs
Master "Binary Tree Postorder Traversal" 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