Binary Search Tree to Min Heap in Kotlin

by

To convert a Binary Search Tree (BST) into a Min Heap, you need to follow these steps:

  1. Traverse the BST in Inorder fashion and store the nodes in an array.
  2. After the inorder traversal is complete, you will have an array of nodes that are sorted in increasing order.
  3. Now, you need to convert the array into a Min Heap. To do this, you need to start from the last element of the array and move towards the first element. For each element, you need to perform the following steps:
  • Swap the element with its parent until the parent is smaller than the current element.
  • Continue this process until you reach the root of the heap.
  • Once you have completed this process for all the elements, your array will be converted into a Min Heap.
  1. Finally, you need to create a new BST using the nodes of the Min Heap. To do this, you can perform a level order traversal of the Min Heap and insert each node into the BST.
Kotlin
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

1. TreeNode Class

This class represents a node in a binary tree. It has three properties: value which stores the value of the node, left which points to the left child of the node, and right which points to the right child of the node.

Kotlin
fun inorderTraversal(root: TreeNode?, nodes: MutableList<TreeNode>) {
    if (root == null) {
        return
    }
    inorderTraversal(root.left, nodes)
    nodes.add(root)
    inorderTraversal(root.right, nodes)
}

2. inorderTraversal Function

This function performs an inorder traversal of a binary tree and stores the nodes in a list. The root parameter is the root of the binary tree and nodes is the list to store the nodes in.

Kotlin
fun convertBSTtoMinHeap(root: TreeNode?) {
    val nodes = mutableListOf<TreeNode>()
    inorderTraversal(root, nodes)
    for (i in nodes.size - 1 downTo 1) {
        val parentIndex = (i - 1) / 2
        if (nodes[i].value < nodes[parentIndex].value) {
            val temp = nodes[i].value
            nodes[i].value = nodes[parentIndex].value
            nodes[parentIndex].value = temp
        }
    }
}

3. convertBSTtoMinHeap Function

This function takes a BST as input and converts it into a Min Heap. It first performs an inorder traversal of the BST to get a sorted list of nodes. It then iterates over the list of nodes from right to left and swaps each node with its parent until the parent is smaller than the node. This process ensures that the resulting tree satisfies the Min Heap property.

Kotlin
fun insertNode(root: TreeNode?, node: TreeNode?): TreeNode? {
    if (root == null) {
        return node
    }
    if (node!!.value < root.value) {
        root.left = insertNode(root.left, node)
    } else {
        root.right = insertNode(root.right, node)
    }
    return root
}

4. insertNode Function

This function takes a root node and a new node as input and inserts the new node into the binary search tree rooted at the root node.

Kotlin
fun levelOrderTraversal(root: TreeNode?) {
    if (root == null) {
        return
    }
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        print("${node.value} ")
        if (node.left != null) {
            queue.addLast(node.left!!)
        }
        if (node.right != null) {
            queue.addLast(node.right!!)
        }
    }
}

5. levelOrderTraversal Function

This function performs a level order traversal of a binary tree and prints the values of each node in the order they are visited.

Kotlin
data class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun convertBSTtoMinHeap(root: TreeNode?) {
    val nodes = mutableListOf<TreeNode>()
    inOrderTraversal(root, nodes)
    for (i in 0 until nodes.size / 2) {
        val leftIndex = i * 2 + 1
        val rightIndex = i * 2 + 2
        if (leftIndex < nodes.size) {
            nodes[i].left = nodes[leftIndex]
        }
        if (rightIndex < nodes.size) {
            nodes[i].right = nodes[rightIndex]
        }
    }
}

fun inOrderTraversal(root: TreeNode?, nodes: MutableList<TreeNode>) {
    if (root == null) {
        return
    }
    inOrderTraversal(root.left, nodes)
    nodes.add(root)
    inOrderTraversal(root.right, nodes)
}

fun levelOrderTraversal(root: TreeNode?) {
    if (root == null) {
        return
    }
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        print("${node.value} ")
        if (node.left != null) {
            queue.addLast(node.left!!)
        }
        if (node.right != null) {
            queue.addLast(node.right!!)
        }
    }
}

fun main() {
    val root = TreeNode(8)
    root.left = TreeNode(3)
    root.right = TreeNode(10)
    root.left!!.left = TreeNode(1)
    root.left!!.right = TreeNode(6)
    root.right!!.right = TreeNode(14)
    root.left!!.right!!.left = TreeNode(4)
    root.left!!.right!!.right = TreeNode(7)
    convertBSTtoMinHeap(root)
    levelOrderTraversal(root)
}

6. main Function

The main function creates a BST, converts it into a Min Heap, creates a new BST using the Min Heap nodes, and performs a level order traversal on the new BST.

main function starts by creating a BST with the following values:

         8
       /   \
      3    10
     / \     \
    1   6    14
       / \
      4   7

This is done by creating a root node with a value of 8, and then adding additional nodes as children to form the BST.

Next, the convertBSTtoMinHeap function is called to convert the BST into a min-heap. This is done by rearranging the nodes in the BST to satisfy the min-heap property.

After the BST has been converted into a min-heap, the for loop iterates over each node in the original BST (which has now been rearranged to form a min-heap). For each node, the insertNode function is called to insert the node into a new BST (represented by the newRoot variable). The insertNode function inserts the node into the correct position in the new BST to maintain the BST property.

Finally, the levelOrderTraversal function is called to perform a level-order traversal of the new BST and print out its values. The output of the code should be: 1 3 4 6 7 8 10 14

min heap :

         1
       /   \
      3     4
     / \   / \
    8   6 7   10
         \
          14

Leave a Comment