Tree: Depth-First Search - Flatten Binary Tree to Linked List
What is the time complexity of the recursive in-place flatten algorithm that uses postorder traversal and rewires pointers by finding the rightmost node of the left subtree at each node?
What is the time complexity of the recursive in-place flatten algorithm that uses postorder traversal and rewires pointers by finding the rightmost node of the left subtree at each node?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze pointer rewiring cost
At each node, finding rightmost node of left subtree can take O(h) in worst case.Step 2: Aggregate over all nodes
In skewed trees, this leads to O(n) nodes x O(n) work = O(n²) time complexity.Final Answer:
Option A -> Option AQuick Check:
Nested traversal causes quadratic time in worst case [OK]
Quick Trick: Repeated rightmost traversal causes O(n²) time [OK]
Common Mistakes:
MISTAKES- Assuming O(n) because each node visited once
- Confusing recursion depth with total work
Trap Explanation:
PITFALL- Candidates often forget the inner loop to find rightmost node causes quadratic time.
Interviewer Note:
CONTEXT- Tests understanding of hidden nested loops in recursive pointer rewiring.
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