348. Convert Binary Search Tree to Sorted Doubly Linked List
You are given the root of a binary search tree in which every node carries an integer val plus left and right pointers. Rewire the tree in place into a circular doubly linked list sorted in ascending order, and return its head — the node holding the smallest value.
Reuse the existing nodes rather than allocating new ones: after the conversion, each node's left pointer must reference its predecessor and its right pointer its successor. Because the list is circular, the largest node's successor is the smallest node, and the smallest node's predecessor is the largest. For a single-node tree, both pointers of that node reference the node itself.
The grader starts at the node you return, follows right pointers all the way around, and checks every left back-link plus the wrap-around to the head; it prints the visited values in order, or invalid if any link is broken.
Example 1:
Input: root = [4, 2, 5, 1, 3]
Output: the node 1, head of the circle 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5
Explanation: Visiting the BST inorder gives 1, 2, 3, 4, 5. The same nodes are rewired in that order, and 5 links back around to 1.
Example 2:
Input: root = [7]
Output: the node 7, whose left and right both point to itself
Explanation: A single node forms a one-element circle: both of its pointers must reference the node itself.
Constraints:
- 1 ≤ number of nodes ≤ 2000
- -10⁵ ≤ Node.val ≤ 10⁵
- All node values are distinct and obey the binary search tree ordering.
Hints:
Which traversal of a BST produces its values in ascending order? That is exactly the order the linked list needs.
Carry a prev pointer through an inorder traversal: on each visit set prev.right = node and node.left = prev, then advance prev. Remember the very first node you touch — it is the head you must return.
When the traversal ends, prev holds the largest node. Close the circle by joining it with the first node before returning.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [4, 2, 5, 1, 3]
Expected output: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 (circular)