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^9root = [4,2,5,1,3]Output[1,2,3,4,5]WhyThe BST's in-order traversal is `1,2,3,4,5`, so the linked list is built in that order.root = [2,1,3]Output[1,2,3]WhyNode `1` is the smallest and becomes the head, followed by `2` and `3`.root = [1]Output[1]WhyA single-node BST becomes a one-node doubly linked list.0 <= number of nodes <= 10^5-10^9 <= node.val <= 10^9The input tree is a valid BSTThe conversion must be done in-place using existing nodesdef bst_to_doubly_linked_list(root):
