114. Flatten Binary Tree to Linked List
You receive the root of a binary tree whose nodes have an integer val and left/right pointers. Rearrange the tree in place so it becomes a right-leaning chain: when your function finishes, every node's left must be null, and following right pointers from the root must visit the nodes in preorder — each node first, then its original left subtree, then its original right subtree.
The chain reuses the very same nodes and the same TreeNode type; do not build a new tree, and do not return anything — mutate the structure you were given. The grader then walks only the right pointers and also checks that no left pointer survived.
Example 1:
Input: root = [1, 2, 5, 3, 4, null, 6]
Output: root rewired to 1 → 2 → 3 → 4 → 5 → 6 (all left pointers null)
Explanation: Preorder visits 1, then the left subtree (2, 3, 4), then the right subtree (5, 6); the chain strings those nodes together on right pointers.
Example 2:
Input: root = [1, null, 2, 3]
Output: root rewired to 1 → 2 → 3
Explanation: Node 2's left child 3 gets spliced onto the right chain immediately after 2, and its left pointer is cleared.
Constraints:
- 0 ≤ number of nodes ≤ 2000
- -100 ≤ Node.val ≤ 100
Hints:
Preorder is 'me, then my left subtree, then my right subtree'. If you had the nodes in that order in a list, relinking them into a right chain is a trivial loop — that is a perfectly valid first solution.
For O(1) extra space, ask where the original right subtree must reattach: right after the *rightmost* node of the left subtree. Splice the left subtree between the node and its right subtree, null the left pointer, step right, repeat.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 5, 3, 4, null, 6]
Expected output: 1 → 2 → 3 → 4 → 5 → 6