DSA problem
Convert Binary Search Tree to Sorted Doubly Linked List
Convert a Binary Search Tree to a sorted circular doubly linked list in place. You can think of the left and right pointers of each node as synonyms of the previous and next pointers in a doubly linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
The transformation must be done in place: you must reuse the same nodes from the BST, only changing how their left and right pointers connect them. Return a pointer to the smallest element of the resulting list.
An in-order traversal of a BST visits nodes in sorted order, which is exactly the order we want them in the doubly linked list. The clean approach maintains a single prev pointer during the in-order walk: at each visited node cur, link prev.right = cur and cur.left = prev, then update prev = cur. The first node visited (the smallest) is also remembered as head.
After the traversal completes, prev points at the largest element. Close the circle by linking prev.right = head and head.left = prev, then return head. The whole conversion runs in O(n) time and O(h) extra space (the recursion stack).
Examples
root = [4,2,5,1,3][1,2,3,4,5]root = [2,1,3][1,2,3]root = [][]Constraints
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
- All the values of the tree are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.