Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a 'linked list' in-place. The 'linked list' should use the right child pointers, and the left child pointers should always be `NULL`.
Why Interviewers Ask This
Google interviewers use this problem to assess a candidate's mastery of pointer manipulation and recursive thinking within constrained memory environments. They specifically evaluate the ability to traverse complex data structures while maintaining in-place modification constraints, which mirrors real-world scenarios where optimizing space complexity is critical for performance.
How to Answer This Question
1. Clarify Requirements: Confirm if the flattening must follow Pre-Order traversal (Root, Left, Right) and verify the 'in-place' constraint with O(1) extra space.
2. Visualize the Transformation: Briefly explain how the tree structure changes, noting that left pointers become null and right pointers form the linear sequence.
3. Propose Solutions: Start with the Recursive approach using Post-Order logic or Morris Traversal. Explicitly mention why you are choosing one over the other based on space complexity trade-offs.
4. Walk Through Logic: Describe the step-by-step pointer reassignment process without writing code immediately. Explain how to handle the connection between the original right subtree and the flattened left subtree.
5. Analyze Complexity: Conclude by stating the Time Complexity (O(N)) and Space Complexity (O(1) for iterative, O(H) for recursive stack).
Key Points to Cover
- Explicitly confirming the Pre-Order traversal requirement before coding
- Demonstrating knowledge of O(1) space complexity solutions like Morris Traversal
- Clearly articulating the pointer reassignment steps without syntax errors
- Handling edge cases like empty trees or nodes with only one child
- Justifying the choice of algorithm based on Google's efficiency standards
Sample Answer
To flatten a binary tree into a linked list in-place, I would first confirm that we need a Pre-Order traversal sequence where each node's left child becomes null and its right child points to the next node in the sequenc…
Common Mistakes to Avoid
- Using extra space with a queue or recursion stack when an O(1) solution exists
- Failing to reconnect the original right subtree to the end of the flattened left subtree
- Confusing Pre-Order traversal order with In-Order or Post-Order sequences
- Modifying the tree structure incorrectly and losing references to subtrees during the process
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.