Tree: Depth-First Search - Flatten Binary Tree to Linked List
What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?
What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Solution:
Step 1: Identify auxiliary space usage
The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.Step 2: Clarify why O(h) not O(1) or O(n)
It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.Final Answer:
Option D -> Option DQuick Check:
Recursion stack space equals tree height h [OK]
Quick Trick: Recursion stack space equals tree height h [OK]
Common Mistakes:
MISTAKES- Assuming O(1) space because of in-place modification
- Confusing recursion stack with explicit data structures
- Assuming balanced tree always so O(log n) space
Trap Explanation:
PITFALL- Option C looks correct because of in-place rewiring, but recursion stack uses O(h) space. Option D assumes balanced tree which is not guaranteed.
Interviewer Note:
CONTEXT- Tests understanding of recursion stack space vs explicit auxiliary space.
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