Convert Binary Search Tree to Sorted Doubly Linked List
Understanding the Problem
We're given a BST and need to rearrange its pointers so it becomes a sorted circular doubly linked list. No new nodes are created. We reuse the existing tree nodes and change what left and right point to: left becomes the prev pointer of the doubly linked list, and right becomes the next pointer.
Since it's a BST, an in-order traversal visits nodes in sorted order. The problem reduces to: visit the nodes in that order, link each one to the node visited before it, and finally connect the head and tail to make the list circular.
Key Constraints:
0 <= number of nodes <= 2000→ The tree can be empty, so every approach must return null for a null root before touching any pointers.-1000 <= Node.val <= 1000→ Values are never added or multiplied, only linked, so the range has no overflow implications.All values are unique→ Each node has a distinct position in the sorted order, so no tie-breaking logic is needed.
Approach 1: In-Order Traversal with List Collection
Intuition
An in-order traversal of the BST visits nodes in sorted order. Collect them into a list, then rewire the pointers in a second pass: walk through the list, set each node's right to the next node and each node's left to the previous node, and connect the first and last nodes to make the list circular.
Separating "get the sorted order" from "link the nodes" keeps each step simple. No pointers change during the traversal itself, so the rewiring cannot interfere with how we walk the tree.
Algorithm
- Handle the edge case: if the root is null, return null.
- Perform an in-order traversal of the BST, collecting all nodes into a list.
- Iterate through the list and link consecutive nodes:
- For each pair of adjacent nodes, set
nodes[i].right = nodes[i+1]andnodes[i+1].left = nodes[i]. - Close the circular connection: set
head.left = tailandtail.right = head. - Return the head (first element in the sorted list).
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once during the in-order traversal, then iterate through the collected list once to rewire pointers. Both passes are O(n).
- Space Complexity: O(n). The list storing all n nodes takes O(n) space. The recursion stack adds O(h) where h is the height of the tree (O(n) worst case for a skewed tree), but the list dominates.
The list of collected nodes is the only reason this approach needs O(n) extra space. The next approach links nodes during the traversal itself and drops that list.
Approach 2: Recursive In-Order with In-Place Linking (Optimal)
Intuition
Instead of collecting all nodes and linking them afterward, we can link nodes together during the in-order traversal itself. During in-order traversal, the previously visited node is exactly the predecessor of the current node in sorted order, so a single pointer to the last processed node is all the state needed to wire up the doubly linked list.
Maintain two pointers: first (the head of the list, the smallest node) and last (the most recently processed node). As we visit each node during in-order traversal:
- Set
last.right = current(the previous node's next pointer) - Set
current.left = last(the current node's prev pointer) - Update
last = current
When the traversal is done, first holds the smallest node and last holds the largest. Connect them to close the circle: first.left = last and last.right = first.
Overwriting pointers in the middle of the traversal is safe because of the order in which they are touched. When the traversal processes a node, its left subtree is already fully visited, so reassigning current.left affects nothing the traversal still needs. Reassigning last.right is also safe: a node's right pointer is only overwritten after the traversal has already descended into its right subtree, and the recursive call inOrder(node.right) received the original child reference before the reassignment. The traversal keeps walking the original tree structure even as the list pointers are written over it.
Algorithm
- Handle the edge case: if the root is null, return null.
- Initialize two pointers:
first = null(will track the smallest node) andlast = null(will track the most recently visited node). - Perform in-order traversal. At each node:
- If
lastis not null, linklast.right = currentandcurrent.left = last. - If
lastis null, this is the first (smallest) node, so setfirst = current. - Update
last = current. - After traversal completes, close the circular link:
first.left = lastandlast.right = first. - Return
first.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once during the in-order traversal. Each visit does O(1) work (pointer reassignment). The final circular connection is O(1).
- Space Complexity: O(h) where h is the height of the tree. The only extra space is the recursion stack. For a balanced BST, h = O(log n). For a skewed tree, h = O(n) in the worst case.
The recursive approach puts the O(h) space on the call stack, which has a fixed limit. The same traversal can run iteratively with an explicit stack on the heap.
Approach 3: Iterative In-Order with Explicit Stack
Intuition
The logic is identical to the recursive approach: traverse in order and link each node to the previously visited one. The difference is that we drive the traversal with our own stack instead of the call stack, using the standard iterative in-order pattern: push nodes while walking left, pop and process, then move to the right child.
The rewiring stays safe here for the same ordering reason as in the recursive version: after processing a node we read current.right to continue the traversal, and that pointer is not overwritten until the next node is popped, which happens after the read. A deeply skewed tree no longer risks overflowing the call stack, since the explicit stack grows on the heap.
Algorithm
- Handle the edge case: if the root is null, return null.
- Initialize a stack, and set
first = null,last = null. - Push nodes: start from root, keep pushing
node.leftuntil we reach null. - Pop a node from the stack. This is the next node in sorted order.
- Link it with
last(same logic as the recursive approach). - Move to
node.rightand repeat step 3. - When the stack is empty and there's no node to process, close the circular connection and return
first.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Every node is pushed onto the stack exactly once and popped exactly once. Processing each node is O(1).
- Space Complexity: O(h) where h is the height of the tree (O(n) worst case for a skewed tree). The explicit stack holds at most h nodes at any time. Same asymptotic bound as the recursive approach, but now the space is on the heap rather than the call stack.