Flatten Binary Tree to Linked List

Problem

Given the root of a binary tree, rearrange its nodes in place so that the tree becomes a single chain: every node's left pointer is None, and following right pointers from the root visits the nodes in the same order as a preorder traversal of the original tree (node, then its left subtree, then its right subtree). Do not allocate new nodes. The function returns nothing; it modifies the tree.

• The tree has at most 3,000 nodes and may be empty.
• Node values are integers between -300 and 300.
• The interviewer will ask for O(1) extra space beyond the input.

Examples

• root = [7, 3, 9, 1, 5, None, 10] → [7, None, 3, None, 1, None, 5, None, 9, None, 10]. Preorder is 7, 3, 1, 5, 9, 10.
• root = [] → [].
• root = [6] → [6]. A single node is already flat.

Hints

1. Write the preorder sequence for a node: node, left subtree, right subtree. In the flattened result, what node must come immediately after the last node of the left subtree?
2. Which node is the last one in the left subtree's preorder? Can you find it by following pointers only?
3. For each node with a left child: find the rightmost node of the left subtree, hang the current right subtree there, move the left subtree to the right, and continue with the new right child. No stack, no recursion.