Merge Two Binary Search Trees - Algorithm, Visualization, Examples

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)