LC 426: Convert Binary Search Tree to Sorted Doubly Linked List
LC 426: Convert Binary Search Tree to Sorted Doubly Linked List
Difficulty: Medium
Category: Tree, Linked List, DFS
Companies: Amazon, Microsoft, Facebook
Problem Statement
Convert a Binary Search Tree to a sorted Circular Doubly Linked List in-place.
Think of the left and right pointers as synonymous to the previous and next 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.
Examples
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
-1000 <= Node.val <= 1000Node.left.val < Node.val < Node.right.val(BST property)1 <= Number of Nodes <= 1000
Clarification Questions
Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:
-
Doubly linked list: What is the structure? (Assumption: Each node has left (prev) and right (next) pointers, circular list)
-
Sorting order: What order should nodes be in? (Assumption: In-order traversal order - sorted ascending by value)
-
Return value: What should we return? (Assumption: Head of the circular doubly linked list - smallest value node)
-
Tree modification: Can we modify the tree? (Assumption: Yes - convert in-place by modifying pointers)
-
Circular list: Should the list be circular? (Assumption: Yes - last node’s right points to first, first node’s left points to last)
Interview Deduction Process (20 minutes)
Step 1: Brute-Force Approach (5 minutes)
Perform in-order traversal to collect all nodes in a list. Then iterate through the list and connect each node to the next node, and connect the last node to the first to make it circular. This approach works but requires O(n) extra space for the list.
Step 2: Semi-Optimized Approach (7 minutes)
Use in-order traversal with a previous pointer: perform in-order traversal, maintaining a pointer to the previously visited node. Connect previous to current and current to previous as we traverse. After traversal, connect the last node to the first. This uses O(1) extra space but requires careful pointer management.
Step 3: Optimized Solution (8 minutes)
Use in-order traversal with global previous pointer: perform in-order traversal, maintaining a global prev pointer. For each node, set prev->right = current and current->left = prev, then update prev = current. After traversal, connect the last node (prev) to the first node (head) to make it circular. This achieves O(n) time with O(h) space for recursion (or O(1) with iterative traversal), which is optimal. The key insight is that in-order traversal visits nodes in sorted order, and we can build the doubly linked list incrementally by connecting nodes as we visit them.
Solution Approaches
Approach 1: Inorder Traversal with Global Variables (Recommended)
Key Insight: Use inorder traversal to visit nodes in sorted order, maintaining first and last nodes to build the doubly linked list.
Algorithm:
- Use inorder traversal to process nodes in sorted order
- Maintain global
firstandlastpointers - For each node, connect it to the previous node
- After traversal, connect first and last to make it circular
Time Complexity: O(n)
Space Complexity: O(h) where h is height of tree
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(!root) return nullptr;
inorder(root);
last->right = first;
first->left = last;
return first;
}
private:
Node* first = nullptr, *last = nullptr;
void inorder(Node* node) {
if(node) {
inorder(node->left);
if(last) {
last->right = node;
node->left = last;
} else {
first = node;
}
last = node;
inorder(node->right);
}
}
};
Approach 2: Inorder Traversal with Return Values
Algorithm:
- Perform inorder traversal
- Return the head and tail of the doubly linked list
- Connect the head and tail to make it circular
Time Complexity: O(n)
Space Complexity: O(h)
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(!root) return nullptr;
Node* head = nullptr;
Node* tail = nullptr;
inorder(root, head, tail);
head->left = tail;
tail->right = head;
return head;
}
private:
void inorder(Node* node, Node*& head, Node*& tail) {
if(!node) return;
inorder(node->left, head, tail);
if(!head) {
head = node;
} else {
tail->right = node;
node->left = tail;
}
tail = node;
inorder(node->right, head, tail);
}
};
Approach 3: Iterative Inorder Traversal
Algorithm:
- Use iterative inorder traversal with stack
- Process nodes in sorted order
- Build doubly linked list incrementally
- Connect first and last nodes
Time Complexity: O(n)
Space Complexity: O(h)
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(!root) return nullptr;
stack<Node*> stk;
Node* first = nullptr;
Node* last = nullptr;
Node* curr = root;
while(curr || !stk.empty()) {
while(curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
if(!first) {
first = curr;
} else {
last->right = curr;
curr->left = last;
}
last = curr;
curr = curr->right;
}
first->left = last;
last->right = first;
return first;
}
};
Algorithm Analysis
Approach Comparison
| Approach | Time | Space | Pros | Cons |
|---|---|---|---|---|
| Global Variables | O(n) | O(h) | Simple, clean | Uses global state |
| Return Values | O(n) | O(h) | No global variables | More complex |
| Iterative | O(n) | O(h) | No recursion | More code |
Key Insights
- Inorder Traversal: BST inorder gives sorted order
- Doubly Linked List: Each node needs left and right pointers
- Circular Connection: Connect first and last nodes
- In-place Transformation: Modify existing tree structure
Implementation Details
Global Variables Approach
Node* first = nullptr, *last = nullptr;
void inorder(Node* node) {
if(node) {
inorder(node->left);
// Process current node
if(last) {
last->right = node;
node->left = last;
} else {
first = node; // First node in sorted order
}
last = node;
inorder(node->right);
}
}
Circular Connection
// After inorder traversal
last->right = first; // Last points to first
first->left = last; // First points to last
return first; // Return smallest element
Edge Cases
- Empty Tree:
nullptr→ returnnullptr - Single Node:
[1]→ circular list with one node - Left Skewed:
[1,null,2,null,3]→ sorted order - Right Skewed:
[1,2,null,3]→ sorted order
Follow-up Questions
- What if the tree wasn’t a BST?
- How would you handle duplicate values?
- What if you needed a non-circular doubly linked list?
- How would you optimize for very large trees?
Related Problems
- LC 114: Flatten Binary Tree to Linked List
- LC 897: Increasing Order Search Tree
- LC 98: Validate Binary Search Tree
Optimization Techniques
- Inorder Traversal: Leverage BST property for sorted order
- Global Variables: Simplify state management
- In-place Transformation: No extra space for new nodes
- Circular Connection: Efficient circular list creation
Code Quality Notes
- Readability: Global variables approach is most intuitive
- Performance: All approaches have O(n) time complexity
- Space Efficiency: O(h) space for recursion stack
- Robustness: Handles all edge cases correctly
This problem demonstrates the power of inorder traversal on BSTs and shows how tree structures can be transformed into linked list structures while maintaining sorted order.