ProgramGuru.org

ProgramGuru.org

Merge Two Binary Search Trees

Visualization

Algorithm Steps

  1. Given two binary search trees, perform an in-order traversal on each tree to obtain two sorted arrays. Use inorder traversal on each tree.
  2. Merge the two sorted arrays into a single sorted array using a merge operation.
  3. Construct a balanced binary search tree from the merged sorted array using a recursive buildBST or sortedArrayToBST function.
  4. The resulting tree is the merged binary search tree.

Merge Two Binary Search Trees - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root, arr):
    if root:
        inorder(root.left, arr)
        arr.append(root.val)
        inorder(root.right, arr)


def mergeArrays(arr1, arr2):
    i = j = 0
    merged = []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged


def sortedArrayToBST(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root


def mergeTwoBSTs(root1, root2):
    arr1, arr2 = [], []
    inorder(root1, arr1)
    inorder(root2, arr2)
    merged = mergeArrays(arr1, arr2)
    return sortedArrayToBST(merged)

# Example usage:
if __name__ == '__main__':
    # BST 1:   2
    #         / \
    #        1   3
    root1 = TreeNode(2, TreeNode(1), TreeNode(3))
    
    # BST 2:   7
    #         / \
    #        6   8
    root2 = TreeNode(7, TreeNode(6), TreeNode(8))
    
    mergedRoot = mergeTwoBSTs(root1, root2)
    result = []
    inorder(mergedRoot, result)
    print(result)