In a Meta interview setting, you are given the root of a binary search tree and must convert it in-place into a sorted doubly linked list. Reuse the existing tree nodes: the left pointer should become prev, and the right pointer should become next.
Return the head of the doubly linked list. The list should be ordered by the BST's in-order traversal. Do not allocate new nodes.
root, the root node of a binary search tree, or nullval, left, and rightExample 1
root = [4,2,5,1,3][1,2,3,4,5]1,2,3,4,5, so the doubly linked list follows that order.Example 2
root = [2,1,3][1,2,3]1 becomes the head, 2 is linked after it, and 3 is the tail.0 <= number of nodes <= 10^5-10^9 <= node.val <= 10^9