Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

1. What is this problem about?

The Flatten Binary Tree to Linked List interview question asks you to take a binary tree and reorganize it into a "linked list" structure in-place. The resulting structure should still use the TreeNode class, where all left pointers are null, and the right pointers form a sequence that matches the Pre-order Traversal of the original tree.

2. Why is this asked in interviews?

Companies like Meta, Amazon, and Microsoft use this to test a candidate's mastery of Binary Tree interview patterns. It evaluations whether you can manipulate pointers to change the shape of a tree while preserving a specific traversal order. It also tests your ability to solve a structural transformation problem with $O(1)$ extra space.

3. Algorithmic pattern used

There are two main approaches:

1. Recursive Post-order (Reverse): Traverse the tree in the order: Right, Left, Root. Maintain a prev pointer to the node processed in the previous step and set root.right = prev.
2. Iterative (Morris-like):
   • For each node, if it has a left child, find the rightmost node in that left subtree.
   • Connect that rightmost node's right pointer to the current node's right child.
   • Move the entire left subtree to the right and set left to null.
   • Move to the next right node.

4. Example explanation

Tree: 1 is root, 2 is left child, 5 is right child. 2 has children 3, 4.

1. At root 1: Left subtree is 2-3-4.
2. Find rightmost of left subtree: 4.
3. Connect 4's right to 1's right (5).
4. Move 1's left (2) to 1's right. Set 1's left to null.
5. New structure: 1 -> 2 -> 3, 2.right -> 4, 4.right -> 5.
6. Repeat for node 2.

5. Common mistakes candidates make

• Losing subtrees: Forgetting to link the right subtree to the tail of the flattened left subtree.
• Not in-place: Using an auxiliary list to store the pre-order traversal and then rebuilding the tree. This uses $O(N)$ extra space and is usually sub-optimal.
• Null pointer errors: Not checking if the left child exists before trying to find its rightmost node.

6. Interview preparation tip

Practice "Morris Traversal" concepts. The idea of "stitching" the right subtree to a predecessor in the left subtree is a powerful technique for tree problems requiring $O(1)$ space. This is a core Tree interview pattern.