Tree: Depth-First Search - Flatten Binary Tree to Linked List
Given the following tree and the optimal flatten function using reverse preorder traversal with a global pointer, what is the output linked list sequence?
Given the following tree and the optimal flatten function using reverse preorder traversal with a global pointer, what is the output linked list sequence?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace reverse preorder traversal
Traverse right subtree (5,6), then left subtree (2,3,4), then root (1), rewiring pointers.Step 2: Verify linked list order
Resulting linked list follows preorder: 1 -> 2 -> 3 -> 4 -> 5 -> 6.Final Answer:
Option B -> Option BQuick Check:
Output matches preorder traversal sequence [OK]
Quick Trick: Reverse preorder traversal yields preorder linked list [OK]
Common Mistakes:
MISTAKES- Mixing left and right subtree order
- Forgetting to nullify left pointers
Trap Explanation:
PITFALL- Candidates often confuse traversal order or forget pointer rewiring sequence.
Interviewer Note:
CONTEXT- Tests ability to mentally execute recursive pointer rewiring code.
Master "Flatten Binary Tree to Linked List" in Tree: Depth-First Search
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Tree: Depth-First Search Quizzes