Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and right pointers as synonymous to the predecessor and successor 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.
We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.
Example 1:
Input: root = [4,2,5,1,3]Output: [1,2,3,4,5] Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
Example 2:
Input: root = [2,1,3] Output: [1,2,3]
Constraints:
[0, 2000].-1000 <= Node.val <= 1000Problem Overview: You’re given the root of a binary search tree. The task is to convert it into a sorted circular doubly linked list in-place. The in-order sequence of the BST must become the order of nodes in the doubly linked list, and the first and last nodes should be connected to make the list circular.
Approach 1: Inorder Traversal + Array (O(n) time, O(n) space)
The simplest way to think about this problem is to first collect nodes in sorted order using an inorder traversal of the BST. Store each visited node in an array. Once traversal finishes, iterate through the array and connect adjacent nodes using left and right pointers to form the doubly linked list. Finally connect the first and last nodes to make the structure circular. This approach is easy to implement but uses extra memory proportional to the number of nodes.
Approach 2: Recursive Inorder DFS (O(n) time, O(h) space)
A more optimal solution links nodes directly during an inorder traversal. Since a BST’s inorder traversal produces nodes in sorted order, maintain two pointers: prev for the previously processed node and head for the smallest node. During DFS, connect prev.right to the current node and current.left to prev. After traversal completes, connect the head and the last node to make the list circular. This method uses recursion from depth-first search and only requires the call stack.
Approach 3: Iterative Inorder with Stack (O(n) time, O(h) space)
If recursion depth is a concern, perform the same inorder traversal iteratively using a stack. Push nodes while moving left, pop to process them in sorted order, and then move to the right subtree. Each popped node is linked with the previously processed node exactly like the recursive solution. The resulting doubly linked list is formed incrementally while traversing the tree.
Approach 4: Morris Traversal (O(n) time, O(1) space)
Morris traversal removes the need for recursion or a stack by temporarily modifying tree pointers to simulate the call stack. As nodes are visited in inorder order, link them directly into the doubly linked list using the same prev pointer technique. After traversal, connect the head and tail to complete the circular list. This achieves constant auxiliary space while preserving the sorted order.
Recommended for interviews: The recursive inorder DFS approach is usually expected. It demonstrates understanding of BST properties and how inorder traversal yields sorted order. Starting with the array-based method shows clear reasoning, but linking nodes during traversal proves stronger algorithmic skill and space optimization.
Java
C++
Go
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal + Array | O(n) | O(n) | Simplest implementation when extra memory is acceptable |
| Recursive Inorder DFS | O(n) | O(h) | Common interview solution using recursion and BST inorder property |
| Iterative Inorder with Stack | O(n) | O(h) | Avoid recursion when stack depth may be large |
| Morris Traversal | O(n) | O(1) | Best when constant extra space is required |
Flatten Binary Tree to Linked List - Leetcode 114 - Python • NeetCode • 56,714 views views
Watch 9 more video solutions →Practice Convert Binary Search Tree to Sorted Doubly Linked List with our built-in code editor and test cases.
Practice on FleetCode