Convert BST to Min Heap in Java
Converting a Binary Search Tree (BST) to a Min Heap in Java involves transforming a tree with the properties of a BST into a binary tree with the properties of a Min Heap. In a BST, for each node, the values in its left subtree are less than its value, and the values in its right subtree are greater. In a Min Heap, for each node, the values of its children are greater than or equal to its own value.
Input
Output
Level Order: 6 7 13 9 12 18 23
Approach 1: Using Linked List Queue
The approach to convert a Binary Search Tree (BST) to a Min Heap using a linked list queue involves two main steps: traversing the BST using a level-order traversal with a queue and then constructing the Min Heap from the collected values. This approach uses a linked list queue to perform the level-order traversal and build the Min Heap in a way that maintains the heap properties.
Algorithm
Step 1: Create a class TreeNode to represent each node in the binary tree. The class contains attributes data, left, and right to store the value of the node and references to its left and right children.
Step 2: Implement a level-order traversal function printLevelOrder to print the elements of the tree in level order. This function uses a queue to process each level and prints the nodes in the order they are encountered during the traversal.
Step 3: Implement an in-order traversal function storeInOrder to store the elements of the tree in an ArrayList. The in-order traversal ensures that elements are stored in sorted order.
Step 4: Implement a function replaceInOrderWithPreOrder to replace the values stored in the ArrayList (in-order traversal) with the values from a pre-order traversal. The replacement is done in-place on the tree nodes.
Step 5: Convert BST to Min Heap (convertBSTToMinHeap function): Create an ArrayList to store the in-order traversal of the BST. Call the storeInOrder function to populate the ArrayList with the in-order traversal.
Step 6: Call the replaceInOrderWithPreOrder function to replace the values in the BST nodes with the values from the in-order traversal.
Step 7: In the main method, create an example BST with nodes having values 12, 7, 18, 6, 9, 13, and 23. Call the convertBSTToMinHeap function to convert the BST to a Min Heap in-place. Call the printLevelOrder function to print the Min Heap elements in level order.
Filename: ConvertBSTToMinHeap.java
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
public class ConvertBSTToMinHeap {
// Class representing a node of a binary tree
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int data) {
this.data = data;
}
}
// Function to print level order traversal of a binary tree
private static void printLevelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
// Function to store the inorder traversal of the tree in a list
private static void storeInOrder(TreeNode root, ArrayList<Integer> inOrder) {
if (root != null) {
storeInOrder(root.left, inOrder);
inOrder.add(root.data);
storeInOrder(root.right, inOrder);
}
}
// Function to replace the inorder traversal with pre-order traversal
private static void replaceInOrderWithPreOrder(TreeNode root, ArrayList<Integer> inOrder) {
if (root != null) {
root.data = inOrder.get(0);
inOrder.remove(0);
replaceInOrderWithPreOrder(root.left, inOrder);
replaceInOrderWithPreOrder(root.right, inOrder);
}
}
// Function to convert the BST to a Min Heap
private static void convertBSTToMinHeap(TreeNode root) {
ArrayList<Integer> inOrderTraversal = new ArrayList<>();
// Store the inorder traversal of the tree in a list
storeInOrder(root, inOrderTraversal);
// Replace the inorder traversal with pre-order traversal
replaceInOrderWithPreOrder(root, inOrderTraversal);
}
public static void main(String[] args) {
// Example Tree
TreeNode root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(18);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(9);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(23);
convertBSTToMinHeap(root);
// Print the Min Heap in level order
System.out.print("Level Order of Min Heap elements after conversion: ");
printLevelOrder(root);
System.out.println();
}
}
Output:
Level Order of Min Heap elements after conversion: 6 7 13 9 12 18 23
Time Complexity
The in-order traversal of the BST has a time complexity of O(N), where N is the number of nodes in the tree and each node is visited exactly once. Replacing in-order values with pre-order values has a time complexity of O(N) and each node's value is replaced once. The dominating factor is the in-order traversal, making the overall time complexity of the algorithm O(N).
Space Complexity
The space complexity of the recursion stack during in-order traversal is determined by the maximum depth of the recursion, which is equal to the height of the BST. In the worst case (skewed tree), it can be O(N), but for balanced trees, it is O(log N).
Approach 2: Using Arrays
The approach of converting a Binary Search Tree (BST) to a Min Heap using arrays involves traversing the BST in an in-order manner, storing the elements in an array, and then modifying the BST nodes based on the array elements to transform it into a Min Heap. This process ensures that the properties of both the BST and Min Heap are preserved.
Algorithm
Step 1: Define a class named BSTtoMinHeapArray and inside the class, define a static nested class TreeNode to represent the nodes of the binary tree.
Step 2: Level Order Traversal: Define a method levelOrderTraversal that performs level order traversal of the tree. Utilize a queue to keep track of nodes during traversal. Print the data of each node during traversal.
Step 3: Inorder Traversal to Array: Define a method inorderTraversal that performs in-order traversal of the BST and stores elements in an array.
Step 4: Utilize an array arr to store the BST elements in sorted order. Maintain an index index to keep track of the current position in the array. Use recursion to traverse the left subtree, store the root data, and traverse the right subtree.
Step 5: Array to Min Heap Conversion: Define a method arrayToMinHeap to convert the array back to the Min Heap structure. Use recursion to traverse the modified BST.
Step 6: Replace each node's data with the corresponding element from the array. Update the index during traversal.
Step 7: Conversion Function: Define a method convertBSTtoMinHeap to initiate the conversion process. Initialize an index array index to keep track of the position in the array.
Step 8: Initialize an array arr to store the BST elements. Call inorderTraversal to fill the array with BST elements. Reset the index to 0. Call arrayToMinHeap to modify the BST nodes using the array.
Step 9: Utility Function - Get Size: Define a utility method getSize to calculate the number of nodes in the tree. Use recursion to count nodes in the left and right subtrees.
Step 10: Inside the main method, create a sample BST. Print the level order traversal before conversion. Call convertBSTtoMinHeap to convert the BST to Min Heap. Print the level order traversal after conversion.
Filename: BSTtoMinHeapArray.java
import java.util.LinkedList;
import java.util.Queue;
public class BSTtoMinHeapArray {
static class TreeNode {
int data;
TreeNode left, right;
TreeNode() {
this.data = 0;
this.left = this.right = null;
}
TreeNode(int data) {
this.data = data;
this.left = this.right = null;
}
}
private static void levelOrderTraversal(TreeNode root) {
if (root == null)
return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null)
queue.add(current.left);
if (current.right != null)
queue.add(current.right);
}
}
private static void inorderTraversal(TreeNode root, int[] arr, int[] index) {
if (root == null)
return;
inorderTraversal(root.left, arr, index);
arr[index[0]++] = root.data;
inorderTraversal(root.right, arr, index);
}
private static void arrayToMinHeap(TreeNode root, int[] arr, int[] index) {
if (root == null)
return;
root.data = arr[index[0]++];
arrayToMinHeap(root.left, arr, index);
arrayToMinHeap(root.right, arr, index);
}
static void convertBSTtoMinHeap(TreeNode root) {
int[] index = { 0 };
int[] arr = new int[getSize(root)];
inorderTraversal(root, arr, index);
index[0] = 0;
arrayToMinHeap(root, arr, index);
}
private static int getSize(TreeNode root) {
if (root == null)
return 0;
return getSize(root.left) + 1 + getSize(root.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(18);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(9);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(23);
System.out.print("Level Order Traversal Before Conversion:" + "\n");
levelOrderTraversal(root);
convertBSTtoMinHeap(root);
System.out.print("\nLevel Order Traversal After Conversion:" + "\n");
levelOrderTraversal(root);
}
}
Output:
Level Order Traversal Before Conversion:
12 7 18 6 9 13 23
Level Order Traversal After Conversion:
6 7 13 9 12 18 23
Time Complexity
The overall time complexity of the provided algorithm for converting a Binary Search Tree (BST) to a Min Heap using arrays is O(N), where N is the number of nodes in the BST. This is because both the in-order traversal and the array-to-Min-Heap conversion processes visit each node exactly once.
Space Complexity
The array arr is used to store the elements of the BST during the in-order traversal. The size of the array is determined by the number of nodes in the BST, which is N. Hence, the overall space required for the array is O(N).
Approach 3: Using Double LinkedList
Converting a Binary Search Tree (BST) into a Min Heap is a fascinating algorithmic problem that involves traversing and manipulating the tree structure to satisfy the properties of both a BST and a Min Heap. In the provided solution, a doubly linked list is employed to facilitate an efficient and organized approach to store and replace tree nodes during the conversion process.
Algorithm
Step 1: A TreeNode class represents a node in the binary tree. It has an integer data field and references to left and right child nodes.
Step 2: ListNode Class: A ListNode class represents a node in the doubly linked list. It contains an integer data, and references to the next and previous nodes.
Step 3: printLevelOrder Function: This function prints the level-order traversal of the binary tree using a standard BFS (Breadth-First Search) approach with a queue.
Step 4: storeInOrder Function: This recursive function performs an in-order traversal of the BST and constructs a doubly linked list to store the elements.
Step 5: The function takes the current root node and the tail of the doubly linked list as parameters. The tail of the doubly linked list is updated during traversal to maintain the order of elements.
Step 6: replaceInOrderWithPreOrder Function: This recursive function replaces the values of the nodes in the binary tree with the values from the doubly linked list in a pre-order traversal manner.
Step 7: It takes the current root node and the head of the doubly linked list as parameters. The head of the doubly linked list is updated during traversal to move to the next element.
Step 8: convertBSTToMinHeap Function: This function initiates the conversion process. It creates a dummy node to start the doubly linked list and calls the storeInOrder function to construct the linked list.
Step 9: Then, it calls the replaceInOrderWithPreOrder function to replace the values in the BST with the values from the linked list.
Step 10: In the main function, an example BST is created. The convertBSTToMinHeap function is called to convert the BST into a Min Heap in-place. Finally, the level-order traversal of the resulting Min Heap is printed.
Filename: BSTToMinHeapDLL.java
import java.util.LinkedList;
import java.util.Queue;
public class BSTToMinHeapDLL {
// Class representing a node of a binary tree
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int data) {
this.data = data;
}
}
// Class representing a doubly linked list node
static class ListNode {
int data;
ListNode next, prev;
public ListNode(int data) {
this.data = data;
this.next = this.prev = null;
}
}
// Function to print level order traversal of a binary tree
private static void printLevelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
// Function to store the inorder traversal of the tree in a doubly linked list
private static ListNode storeInOrder(TreeNode root, ListNode tail) {
if (root != null) {
tail = storeInOrder(root.left, tail);
ListNode newNode = new ListNode(root.data);
if (tail != null) {
tail.next = newNode;
newNode.prev = tail;
}
return storeInOrder(root.right, newNode);
}
return tail;
}
// Function to replace the inorder traversal with pre-order traversal using a doubly linked list
private static ListNode replaceInOrderWithPreOrder(TreeNode root, ListNode head) {
if (root != null && head != null) {
root.data = head.data;
head = replaceInOrderWithPreOrder(root.left, head.next);
return replaceInOrderWithPreOrder(root.right, head);
}
return head;
}
// Function to convert the BST to a Min Heap using a doubly linked list
private static void convertBSTToMinHeap(TreeNode root) {
ListNode head = new ListNode(-1); // Dummy node to start the doubly linked list
ListNode tail = storeInOrder(root, head);
replaceInOrderWithPreOrder(root, head.next);
}
public static void main(String[] args) {
// Example Tree
TreeNode root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(18);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(9);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(23);
convertBSTToMinHeap(root);
// Print the Min Heap in level order
System.out.print("Level Order of Min Heap elements after conversion: ");
printLevelOrder(root);
System.out.println();
}
}
Output:
Level Order of Min Heap elements after conversion: 6 7 13 9 12 18 23
Time Complexity
The time complexity of the provided algorithm is O(N), where N is the number of nodes in the binary tree. Both the in-order traversal to construct the doubly linked list and the pre-order traversal to replace values take O(N) time each. The operations within each node (updating values, traversing the linked list) are constant time.
Space Complexity
The space complexity of the given algorithm is O(n), where n is the number of nodes in the binary tree (BST). The doubly linked list is used to store the elements of the BST during the conversion process. The space required for the linked list is directly proportional to the number of nodes in the tree, resulting in O(n) space complexity.
Approach 4: Using Array List
The approach of converting a Binary Search Tree (BST) to a Min Heap using only an ArrayList involves two main steps: first, performing an in-order traversal of the BST to store its elements in an ArrayList, and second, using the ArrayList to update the values of the BST nodes in a way that satisfies the Min Heap property.
Algorithm
Step 1: Create a class TreeNode to represent each node in the binary tree with attributes data, left, and right.
Step 2: Implement a function inOrderTraversal to perform an in-order traversal of the BST. During the traversal, store the values of the BST nodes in an ArrayList. The in-order traversal ensures that the elements are stored in sorted order.
Step 3: Implement a function convertListToMinHeap to update the values of the BST nodes with the corresponding values from the ArrayList to achieve a Min Heap.
Step 4: Start with the root of the BST and set its value to the first element in the ArrayList. Recursively update the left and right children using the next elements from the ArrayList. Continue this process until all nodes in the BST are updated.
Step 5: Implement a function convertBSTtoMinHeap that takes the root of the BST as an argument. Perform in-order traversal using the inOrderTraversal function and store the elements in an ArrayList.
Step 6: Call the convertListToMinHeap function to update the BST nodes with values from the ArrayList.
Step 7: Implement a function printMinHeapOrder to print the elements of the Min Heap in order. Perform an in-order traversal and print each node's value.
Step 8: In the main method, create an example BST. Call convertBSTtoMinHeap on the root of the BST. Print the Min Heap elements after conversion.
Filename: BSTtoMinHeapArrayList.java
import java.util.ArrayList;
public class BSTtoMinHeapArrayList {
static class TreeNode {
int data;
TreeNode left, right;
TreeNode() {
this.data = 0;
this.left = this.right = null;
}
TreeNode(int data) {
this.data = data;
this.left = this.right = null;
}
}
private static void levelOrderTraversal(TreeNode root) {
if (root == null)
return;
ArrayList<TreeNode> levelOrderList = new ArrayList<>();
levelOrderList.add(root);
int index = 0;
while (index < levelOrderList.size()) {
TreeNode current = levelOrderList.get(index);
System.out.print(current.data + " ");
if (current.left != null)
levelOrderList.add(current.left);
if (current.right != null)
levelOrderList.add(current.right);
index++;
}
}
private static void inorderTraversal(TreeNode root, ArrayList<Integer> arr) {
if (root == null)
return;
inorderTraversal(root.left, arr);
arr.add(root.data);
inorderTraversal(root.right, arr);
}
static int index;
private static void arrayToMinHeap(TreeNode root, ArrayList<Integer> arr) {
if (root == null)
return;
root.data = arr.get(index++);
arrayToMinHeap(root.left, arr);
arrayToMinHeap(root.right, arr);
}
static void convertBSTtoMinHeap(TreeNode root) {
index = 0;
ArrayList<Integer> arr = new ArrayList<>();
inorderTraversal(root, arr);
arrayToMinHeap(root, arr);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(18);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(9);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(23);
System.out.print("Level Order Traversal Before Conversion:" + "\n");
levelOrderTraversal(root);
convertBSTtoMinHeap(root);
System.out.print("\nLevel Order Traversal After Conversion:" + "\n");
levelOrderTraversal(root);
}
}
Output:
Level Order Traversal Before Conversion:
12 7 18 6 9 13 23
Level Order Traversal After Conversion:
6 7 13 9 12 18 23
Time Complexity
The in-order traversal of the Binary Search Tree (BST) has a time complexity of O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the traversal. The conversion process involves updating each node of the BST once, resulting in a time complexity of O(N). The overall time complexity is O(N).
Space Complexity
The overall space complexity is influenced by the space required for the ArrayList and the recursion stack during in-order traversal and Min Heap conversion. The algorithm is relatively efficient in terms of space, especially when the tree is balanced. However, in the worst case of a skewed tree, the space complexity may approach O(N).