Convert Binary Search Tree to Sorted Doubly Linked List
Medium · Trees · Linked List · Stack · Tree · Depth-First Search · Binary Search Tree · Doubly-Linked List
Problem
Given the root of a binary search tree, rearrange its nodes in place into a sorted, circular, doubly linked list, and return the node with the smallest value.
Reuse the tree's own nodes: treat left as the "previous" pointer and right as the "next" pointer. The list is circular: the smallest node's left points to the largest node, and the largest node's right points back to the smallest. Do not create new nodes. For an empty tree, return None.
The tree is given in level order, with None for a missing child; from_level([4,2,5]) builds it. The output lists the values met by following right pointers once around the list from the returned node; to_ring(head) does that for you. The judge also checks every left pointer and that the list closes on itself.
Examples
Input: root = [6,3,8,1,4] Output: [1,3,4,6,8]
In-order the values are 1, 3, 4, 6, 8: the list runs 1 3 4 6 8, and 8 links back to 1.
Input: root = [5] Output: [5]
A single node points to itself in both directions.
Input: root = [] Output: []
There is nothing to link: return None.
Constraints
- 0 <= number of nodes <= 2000
- -1000 <= Node.val <= 1000
- all values are distinct
Approaches
- Baseline: collect, sort, relink — time O(n log n), space O(n)
Follow-up
The iterative in-order walk uses O(h) extra space. A Morris traversal brings it to O(1), at the cost of temporarily threading the tree. The use cases put the same in-order idea to work on plain values: merging two search trees into one sorted list, and the smallest gap between any two values.
Related problems
Start free on Cariara · Coding problems · System design studio
