Binary Search TreesProblem 22 of 22
Flatten BST to sorted list
Problem Statement
Given a BST, convert it to a sorted singly linked list or a sorted doubly linked list (flatten the BST). The conversion should be done in-place using the tree's left/right pointers as prev/next pointers.
Example:
BST: Sorted List:
5
/ \
3 7 1 <-> 3 <-> 5 <-> 7 <-> 10
/ \ \
1 4 10
Inorder: [1, 3, 4, 5, 7, 10]
Flattened to sorted linked list
Approach 1: Brute Force (Inorder to Array, Build List)
Intuition
Extract all nodes via inorder traversal (sorted), then build a new linked list.
Algorithm
- Perform inorder traversal to get sorted nodes
- Create linked list from the array
- Optionally free old tree structure
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<TreeNode> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root);
inorder(root.right, nodes);
}
public TreeNode flattenBSTBruteForce(TreeNode root) {
if (root == null) return null;
List<TreeNode> nodes = new ArrayList<>();
inorder(root, nodes);
// Build linked list
for (int i = 0; i < nodes.size(); i++) {
nodes.get(i).left = (i > 0) ? nodes.get(i-1) : null;
nodes.get(i).right = (i < nodes.size() - 1) ? nodes.get(i+1) : null;
}
return nodes.get(0);
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n) - Storing all nodes
Approach 2: Optimal (In-place using Recursion)
Intuition
During inorder traversal, link nodes directly without storing them. Use a prev pointer to track the previously visited node.
Algorithm
- Perform inorder traversal
- Maintain prev pointer to last processed node
- Link current node: prev.right = current, current.left = prev
- Update prev to current
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode head = null;
private TreeNode prev = null;
private void inorderLink(TreeNode root) {
if (root == null) return;
// Process left subtree
inorderLink(root.left);
// Process current node
if (prev == null) {
head = root;
} else {
prev.right = root;
root.left = prev;
}
prev = root;
// Process right subtree
inorderLink(root.right);
}
public TreeNode flattenBST(TreeNode root) {
head = null;
prev = null;
inorderLink(root);
return head;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(h) - Recursion stack
Approach 3: Morris Traversal (True O(1) Space)
Intuition
Use Morris traversal to achieve O(1) extra space. Create threaded links temporarily, then convert to final linked list.
Algorithm
- Use Morris inorder traversal
- As we visit each node, link to previous node
- No extra space except for prev pointer
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode flattenBSTMorris(TreeNode root) {
TreeNode head = null;
TreeNode prev = null;
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
// Process current node
if (prev == null) {
head = curr;
} else {
prev.right = curr;
curr.left = prev;
}
prev = curr;
curr = curr.right;
} else {
// Find inorder predecessor
TreeNode pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
if (prev == null) {
head = curr;
} else {
prev.right = curr;
curr.left = prev;
}
prev = curr;
curr = curr.right;
}
}
}
return head;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1) - No extra space
Approach 4: Flatten to Singly Linked List (Right-skewed)
Intuition
If we only need a singly linked list (using only right pointers), we can simplify.
Algorithm
- Perform reverse inorder (right -> root -> left)
- Prepend each node to the result
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode head = null;
private void reverseInorder(TreeNode root) {
if (root == null) return;
reverseInorder(root.right);
// Prepend current node
root.right = head;
root.left = null;
head = root;
reverseInorder(root.left);
}
public TreeNode flattenToSinglyList(TreeNode root) {
head = null;
reverseInorder(root);
return head;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(h) for recursion
Approach 5: Make Circular DLL
Intuition
For circular DLL, connect the last node back to the first.
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode head = null;
private TreeNode prev = null;
private void inorderLink(TreeNode root) {
if (root == null) return;
inorderLink(root.left);
if (prev == null) {
head = root;
} else {
prev.right = root;
root.left = prev;
}
prev = root;
inorderLink(root.right);
}
public TreeNode treeToCircularDLL(TreeNode root) {
if (root == null) return null;
head = null;
prev = null;
inorderLink(root);
// Make circular
prev.right = head;
head.left = prev;
return head;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(h)
Key Takeaways
- Inorder gives sorted: BST inorder traversal is sorted
- In-place conversion: Use left as prev, right as next
- Morris for O(1) space: True constant space but more complex
- Variations: Singly list, doubly list, circular list
- Related to LeetCode #426 - Convert BST to Sorted Doubly Linked List
- Reverse inorder trick: For building list from tail to head
- The prev pointer pattern is key for linking during traversal