Practice/Meta/Leetcode 426. Convert Binary Search Tree to Sorted Doubly Linked List

Leetcode 426. Convert Binary Search Tree to Sorted Doubly Linked List

CodingMust

Problem

You are given the root of a binary search tree. Your task is to transform this tree into a sorted circular doubly linked list in-place.

In the resulting list:

• Each node's left pointer should act as the prev pointer in the doubly linked list
• Each node's right pointer should act as the next pointer in the doubly linked list
• The list should be sorted in ascending order based on the node values
• The list should be circular: the smallest element's left should point to the largest element, and the largest element's right should point to the smallest element

Return the pointer to the smallest element in the resulting circular doubly linked list.

Requirements

1. Convert the BST to a sorted circular doubly linked list in-place
2. Use the existing node structure (reuse left and right pointers)
3. Return the head of the circular list (the node with the smallest value)
4. If the input tree is empty, return null
5. The resulting list must be both doubly-linked and circular

Constraints

• The number of nodes in the tree is in the range [0, 2000]
• -1000 <= Node.val <= 1000
• All values in the BST are unique
• You must solve it with O(1) extra space (excluding recursion stack)

Examples

Example 1:

` Input: 4 /
2 5 /
1 3

Output: Head pointing to node with value 1, where: 1.left = 5, 1.right = 2 2.left = 1, 2.right = 3 3.left = 2, 3.right = 4 4.left = 3, 4.right = 5 5.left = 4, 5.right = 1

Explanation: The BST is converted to a circular doubly linked list in sorted order: 1 <-> 2 <-> 3 <-> 4 <-> 5, with the last node connecting back to the first. `

Example 2:

` Input: 2 /
1 3

Output: Head pointing to node with value 1, where: 1.left = 3, 1.right = 2 2.left = 1, 2.right = 3 3.left = 2, 3.right = 1

Explanation: Three nodes form a circular doubly linked list: 1 <-> 2 <-> 3. `

Example 3:

` Input: null

Output: null

Explanation: Empty tree results in null. `