Rearrange a binary search tree with distinct values into a chain: the smallest value becomes the new root, no node has a left child, and each node's right child is the next larger value. Reuse the existing nodes (relink them, do not create new ones) and return the new root.
Examples
5
/ \ 3
3 8 ==> \
\ 4
4 \
5
\
8
Input: root = build_tree([5, 3, 8, None, 4])
Output: tree_to_list(...) == [3, None, 4, None, 5, None, 8]
Input: root = build_tree([])
Output: []
Constraints
0 <= number of nodes <= 1000- All values are distinct integers
- O(n) time
Goals
- Relink existing nodes in inorder order
- Clear every left pointer so the result is a right-leaning chain