HeapProblem 15 of 18
Convert BST to Min Heap
Problem Statement
Given a Binary Search Tree (BST), convert it to a Min Heap while maintaining the following properties:
- All values in left subtree should be less than values in right subtree
- The heap should be a complete binary tree
Example:
- Input BST:
4 / \ 2 6 / \ / \ 1 3 5 7 - Output Min Heap:
1 / \ 2 3 / \ / \ 4 5 6 7 - Explanation: Inorder of BST is [1,2,3,4,5,6,7]. This becomes the level-order of min-heap.
Approach 1: Using Array (Brute Force)
Intuition
Extract all elements from BST using inorder traversal (gives sorted order). Then build the min-heap array and reconstruct the tree.
Algorithm
- Do inorder traversal of BST → sorted array
- Build min-heap from sorted array (sorted array's level-order gives min-heap for this special case)
- Build complete binary tree from level order
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
private void inorderTraversal(TreeNode root, List<Integer> arr) {
if (root == null) return;
inorderTraversal(root.left, arr);
arr.add(root.val);
inorderTraversal(root.right, arr);
}
private TreeNode buildTree(List<Integer> arr) {
if (arr.isEmpty()) return null;
TreeNode root = new TreeNode(arr.get(0));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.size()) {
TreeNode curr = queue.poll();
// Add left child
if (i < arr.size()) {
curr.left = new TreeNode(arr.get(i++));
queue.offer(curr.left);
}
// Add right child
if (i < arr.size()) {
curr.right = new TreeNode(arr.get(i++));
queue.offer(curr.right);
}
}
return root;
}
public TreeNode convertBSTToMinHeap(TreeNode root) {
List<Integer> arr = new ArrayList<>();
inorderTraversal(root, arr);
return buildTree(arr);
}
}Complexity Analysis
- Time Complexity: O(n) - Inorder traversal O(n), building tree O(n)
- Space Complexity: O(n) - For array and queue
Approach 2: In-Place Conversion (Optimal)
Intuition
Since inorder of BST gives sorted order, we can do a preorder traversal of the tree and fill values from the inorder array. This converts BST to min-heap in-place.
Algorithm
- Get inorder traversal (sorted values)
- Do preorder traversal and replace each node's value with next value from sorted array
- The resulting tree is a min-heap (complete binary tree with min-heap property)
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
private int index;
private void inorderTraversal(TreeNode root, List<Integer> arr) {
if (root == null) return;
inorderTraversal(root.left, arr);
arr.add(root.val);
inorderTraversal(root.right, arr);
}
private void preorderFill(TreeNode root, List<Integer> arr) {
if (root == null) return;
root.val = arr.get(index++);
preorderFill(root.left, arr);
preorderFill(root.right, arr);
}
public void convertBSTToMinHeap(TreeNode root) {
List<Integer> arr = new ArrayList<>();
inorderTraversal(root, arr);
index = 0;
preorderFill(root, arr);
}
}Complexity Analysis
- Time Complexity: O(n) - Two traversals of the tree
- Space Complexity: O(n) - For storing sorted array (O(h) for recursion if we don't count array)
Approach 3: Morris Traversal (Space Optimized)
Intuition
Use Morris traversal to get inorder without recursion stack, then fill using iterative preorder.
Algorithm
- Morris inorder traversal to get sorted array
- Morris preorder traversal to fill values
- Achieves O(1) auxiliary space (excluding the array)
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
public void convertBSTToMinHeap(TreeNode root) {
List<Integer> arr = new ArrayList<>();
// Morris Inorder
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
arr.add(curr.val);
curr = curr.right;
} else {
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;
arr.add(curr.val);
curr = curr.right;
}
}
}
// Morris Preorder Fill
curr = root;
int[] idx = {0};
while (curr != null) {
if (curr.left == null) {
curr.val = arr.get(idx[0]++);
curr = curr.right;
} else {
TreeNode pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
curr.val = arr.get(idx[0]++);
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
curr = curr.right;
}
}
}
}
}Complexity Analysis
- Time Complexity: O(n) - Each node visited constant times
- Space Complexity: O(n) for array, O(1) auxiliary space for traversal
Key Takeaways
- Inorder of BST is sorted - This is the key insight
- Sorted array placed in preorder gives min-heap with left < right property
- Converting BST to min-heap preserves the "left values < right values" property
- This is different from standard heapify - we maintain BST-like ordering in subtrees
- The resulting structure is a complete binary tree (heap structure) with min-heap property
- Morris traversal can reduce space complexity but increases code complexity
- This problem combines BST and Heap concepts