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 sequence.
I propose using the Morris Traversal technique or a modified Pre-Order approach to achieve O(1) space complexity, which aligns well with Google's focus on efficiency. The core logic involves finding the rightmost node of the current node's left subtree. Once found, we attach the original right subtree to this rightmost node. Then, we move the entire left subtree to the right position and set the left pointer to null. We repeat this process moving down the right spine of the tree.
For example, consider a root with value 1, a left child 2, and a right child 3. Node 2 has children 4 and 5. We find the rightmost node of 2's left subtree (which is 5), attach 3 to it, then move 2 to the right of 1, making 1->2->4->5->3. This ensures we visit every node exactly once, resulting in O(N) time complexity and strictly O(1) auxiliary space, demonstrating strong control over memory management.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.