545. Increasing Order Search Tree
Given the root of a binary search tree, rearrange its nodes into a single descending-to-the-right chain: the new root is the smallest value, every node's left pointer is null, and every node's right pointer leads to the next-larger value. Return the root of the rearranged tree.
The chain must contain exactly the original values in increasing order — which is the tree's in-order traversal.
The answer is printed as the level-order traversal of the tree you return, so a correct chain prints as the values in increasing order.
Example 1:
Input: root = [5, 3, 6, 2, 4, null, 8]
Output: [2, null, 3, null, 4, null, 5, null, 6, null, 8]
Explanation: The in-order traversal of the tree is 2, 3, 4, 5, 6, 8. The rearranged tree starts at 2 and every node hangs off the previous node's right pointer.
Example 2:
Input: root = [2, 1, 3]
Output: [1, null, 2, null, 3]
Explanation: In-order gives 1, 2, 3, so the new tree is the chain 1 → 2 → 3 through right pointers.
Constraints:
- 1 ≤ number of nodes ≤ 100
- 0 ≤ node values ≤ 1000
- The input is a valid binary search tree.
Hints:
Which traversal of a BST visits values in increasing order? That traversal order is exactly the order of the chain.
Easy version: collect the in-order values into a list, then build a brand-new right-only chain from the list.
In-place version: do the in-order walk keeping a `tail` pointer to the last node of the chain built so far. At each visited node, clear its left pointer and attach it as `tail.right`. A dummy pre-head node avoids special-casing the first node.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 3, 6, 2, 4, null, 8]
Expected output: [2, null, 3, null, 4, null, 5, null, 6, null, 8]