If the binary tree nodes can have parent pointers in addition to left and right children, which modification to the iterative one-stack postorder traversal algorithm can eliminate the need for the last_visited variable?
hard🎤 Interviewer Follow-up Q15 of Q15
Tree: Depth-First Search - Binary Tree Postorder Traversal
If the binary tree nodes can have parent pointers in addition to left and right children, which modification to the iterative one-stack postorder traversal algorithm can eliminate the need for the last_visited variable?
AUse the parent pointer to move back up after visiting a node's children, tracking traversal direction
BPush nodes twice onto the stack to simulate postorder without tracking last visited
CPerform a preorder traversal and reverse the output list at the end
DUse two stacks: one for traversal and one for output, ignoring parent pointers
Step-by-Step Solution
Step 1: Understand role of last_visited
Last_visited tracks if right child was processed to avoid revisiting; parent pointers can provide traversal direction.
Step 2: Use parent pointer to detect traversal direction
By moving up via parent pointer, algorithm knows if coming from left or right child, eliminating need for last_visited.
Step 3: Compare other options
Options B and D ignore parent pointers; A reverses preorder but does not leverage parent pointers; C uses parent pointers effectively.
Final Answer:
Option A -> Option A
Quick Check:
Parent pointers enable direction-aware traversal without extra state [OK]
