Problem

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.

Formal Specification

• Input: root, the root node of a BST, or null
• Output: The head node of a sorted doubly linked list formed from the same nodes
• Reuse each node's left and right pointers as prev and next
• The conversion must be done in-place

Examples

Example 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.

Constraints

• 0 <= number of nodes <= 10^5
• -10^9 <= node.val <= 10^9
• The input tree is a valid BST
• The solution must reuse existing nodes and pointers