Merge Two Binary Search Tree in Kotlin

To merge two binary search trees, you can perform an in-order traversal on both trees and merge the resulting sorted arrays. Then, you can construct a new binary search tree from the sorted array using a modified version of the binary search tree creation algorithm.

Here’s the general algorithm to merge two binary search trees:

Perform an in-order traversal on both trees to create two sorted arrays.
Merge the two sorted arrays into a single sorted array.
Construct a new binary search tree from the sorted array using a modified version of the binary search tree creation algorithm.

The time complexity of merging two binary search trees of size m and n is O(m + n) because we are visiting each node in both trees only once while traversing and merging them.

Example :

First binary search tree:
          5
        /   \
       3     7
      / \
     2   4

Second binary search tree:
         10
        /  \
       8   12
      / \
     6   9

Merged binary search tree:
          8
        /   \
       5    10
      / \    \
     3   7   12
    / \  /
   2  4 6
     \
      9

Kotlin

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
    // Perform in-order traversal on both trees and create two sorted arrays
    val arr1 = mutableListOf<Int>()
    val arr2 = mutableListOf<Int>()
    inOrderTraversal(root1, arr1)
    inOrderTraversal(root2, arr2)
    // Merge the two sorted arrays into a single sorted array
    val mergedArray = mergeSortedArrays(arr1, arr2)
    // Construct a new binary search tree from the sorted array
    return createBSTFromSortedArray(mergedArray, 0, mergedArray.size - 1)
}
// Perform in-order traversal on a tree and add the node values to a list
fun inOrderTraversal(root: TreeNode?, arr: MutableList<Int>) {
    if (root == null) {
        return
    }
    inOrderTraversal(root.left, arr)
    arr.add(root.`val`)
    inOrderTraversal(root.right, arr)
}
// Merge two sorted arrays into a single sorted array
fun mergeSortedArrays(arr1: List<Int>, arr2: List<Int>): List<Int> {
    val merged = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] < arr2[j]) {
            merged.add(arr1[i])
            i++
        } else {
            merged.add(arr2[j])
            j++
        }
    }
    while (i < arr1.size) {
        merged.add(arr1[i])
        i++
    }
    while (j < arr2.size) {
        merged.add(arr2[j])
        j++
    }
    return merged
}
// Create a new binary search tree from a sorted array
fun createBSTFromSortedArray(arr: List<Int>, start: Int, end: Int): TreeNode? {
    if (start > end) {
        return null
    }
    val mid = start + (end - start) / 2
    val root = TreeNode(arr[mid])
    root.left = createBSTFromSortedArray(arr, start, mid - 1)
    root.right = createBSTFromSortedArray(arr, mid + 1, end)

    return root
}
fun main() {
    // Create the first binary search tree
    val root1 = TreeNode(5)
    root1.left = TreeNode(3)
    root1.right = TreeNode(7)
    root1.left?.left = TreeNode(2)
    root1.left?.right = TreeNode(4)
    // Create the second binary search tree
    val root2 = TreeNode(10)
    root2.left = TreeNode(8)
    root2.right = TreeNode(12)
    root2.left?.left = TreeNode(6)
    root2.left?.right = TreeNode(9)
    // Merge the two binary search trees
    val mergedRoot = mergeTrees(root1, root2)
    // Print the merged binary search tree in inorder traversal
    printInorder(mergedRoot)
}
// Utility function to print the binary search tree in inorder traversal
fun printInorder(root: TreeNode?) {
    if (root != null) {
        printInorder(root.left)
        print("${root.`val`} ")
        printInorder(root.right)
    }
}

The given code mergeTrees function takes two binary search tree roots root1 and root2 as input and returns the root of a new binary search tree that is a merge of the two input trees. The steps involved in the mergeTrees function are:

Create two empty lists arr1 and arr2.
Traverse the first binary search tree root1 in in-order fashion and add each node’s value to list arr1 by calling the inOrderTraversal function.
Traverse the second binary search tree root2 in in-order fashion and add each node’s value to list arr2 by calling the inOrderTraversal function.
Merge the two sorted lists arr1 and arr2 into a single sorted list mergedArray by calling the mergeSortedArrays function.
Construct a new binary search tree from the sorted list mergedArray using the createBSTFromSortedArray function, which recursively splits the list into two halves and creates a new node with the middle element, and recursively builds the left and right subtrees using the left and right halves of the list.

The inOrderTraversal function performs an in-order traversal of a binary search tree and adds the values of each node to the input list arr. The mergeSortedArrays function takes two sorted lists as input and merges them into a single sorted list using a merge algorithm similar to merge-sort. The createBSTFromSortedArray function takes a sorted list and recursively creates a new binary search tree from it using the middle element as the root, and the left and right halves of the list as the left and right subtrees, respectively.

Finally, the mergeTrees function returns the root of the new binary search tree that is a merge of the two input trees.

This code creates two binary search trees and merges them using the mergeTrees function. The merged binary search tree is then printed in inorder traversal using the printInorder function. 2 3 4 5 6 7 8 9 10 12

Leave a Comment Cancel reply