Convert Binary Search Tree to Sorted Doubly Linked List
MediumArrayTwo PointersBinary SearchSortingLinked ListTree
Description
Given an array root, convert a binary search tree to a sorted circular doubly-linked list in-place. The left pointer is prev, right is next. Return the result as an array.
Examples
Input:
root = [4,2,5,1,3]Output:
[1,2,3,4,5]Explanation:
In-order traversal of a BST visits nodes in ascending sorted order (left subtree, root, right subtree). During traversal, each node's left pointer is linked to its predecessor and right pointer to its successor, converting the tree structure into a doubly-linked list while preserving the sorted sequence.
Input:
root = [1]Output:
[1]Explanation:
Edge case with a single-element array.
Input:
root = [10,6,14,4,8,12,16]Output:
[4,6,8,10,12,14,16]Explanation:
A complete binary search tree with 7 nodes. The in-order traversal visits left subtree, root, then right subtree, producing the sorted sequence. This demonstrates the algorithm working on a balanced, multi-level tree structure.
Constraints
- •
0 ≤ nodes ≤ 2000