Flatten Binary Tree to Linked List (In-place)

Data Structures
Medium
Amazon
88.8K views

Flatten a binary tree into a single singly linked list in-place. The list should use the right pointer and the order should be the same as preorder traversal.

Why Interviewers Ask This

Amazon interviewers ask this to evaluate your mastery of pointer manipulation and in-place algorithmic optimization. They specifically test if you can transform complex tree structures into linear lists without allocating extra memory, a skill critical for high-performance systems. This problem also assesses your ability to handle recursive logic while managing edge cases like null pointers and ensuring the right pointer correctly links nodes in preorder sequence.

How to Answer This Question

1. Clarify Requirements: Confirm the output must be preorder traversal using only the 'right' pointer for the next node and 'left' set to null. Ask about constraints on memory usage. 2. Choose Strategy: Propose two approaches. First, a simple recursion with O(N) space due to the call stack. Second, an optimal Morris Traversal or iterative approach achieving O(1) space, which Amazon values for efficiency. 3. Walk Through Logic: For the optimal solution, explain how to find the inorder predecessor (the rightmost node in the left subtree). If its right pointer is null, redirect it to the current node's right child, then move the current node's right to its left child, and clear the left pointer. 4. Handle Edge Cases: Explicitly mention handling empty trees, single-node trees, and nodes with only right children. 5. Code Implementation: Write clean code with comments explaining the pointer reassignment steps, emphasizing the in-place nature of the transformation.

Key Points to Cover

  • Demonstrating understanding of preorder traversal mechanics before coding
  • Proposing an O(1) space solution rather than relying on recursion stack
  • Explicitly handling the re-linking of the rightmost node in the left subtree
  • Ensuring the left pointer is cleared to prevent cycles or memory leaks
  • Discussing edge cases like empty trees or skewed trees proactively

Sample Answer

To flatten this binary tree in-place, I will first clarify that we need the result to follow preorder traversal order using only the right pointers. A naive recursive solution would work but uses O(H) stack space. Given…

Common Mistakes to Avoid

  • Allocating a new array or list to store the result, violating the in-place constraint
  • Confusing preorder with inorder or postorder traversal sequences during pointer linking
  • Failing to update the right pointer of the predecessor node before moving the left subtree
  • Not clearing the left pointer after moving the subtree, leaving dangling references

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.

Try it free

Related Interview Questions

How do you implement a queue using two stacks?

Medium
Goldman Sachs

Find K Closest Elements (Heaps)

Medium
Meta

Convert Binary Tree to Doubly Linked List in Place

Hard
Microsoft
Browse all 166 Data Structures questionsBrowse all 184 Amazon questions
Try this question free