At Meta, you may need to transform ordered tree-based data into a sequential structure for efficient traversal. Given the root of a binary search tree (BST), convert it in-place into a sorted doubly linked list using the tree nodes themselves.
The doubly linked list must use the BST's left pointer as prev and right pointer as next. Return the head of the list. The resulting list should be sorted in ascending order. Do not create new nodes.
root, the root node of a BST, or nullleft and right pointers as prev and nextExample 1
Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: An in-order traversal of the BST yields sorted order, and the nodes are linked in that order.
Example 2
Input: root = [2,1,3]
Output: [1,2,3]
Explanation: Node 1 becomes the head, 2 is in the middle, 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 doubly linked list follows that order.root = [2,1,3]Output[1,2,3]WhyThe smallest node `1` becomes the head, then `2`, then `3`.0 <= number of nodes <= 10^5-10^9 <= node.val <= 10^9The input tree is a valid BSTDo not allocate new tree/list nodesdef bst_to_doubly_linked_list(root):
