Merge Two Balanced Binary Search Trees

Data Structures and Algorithms Note

Create a balanced BST by input

def insert(root, val):
    if not root:
        return Node(val)
    if root.val == val:
        return root
    elif root.val > val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

Get an array that uses inorder traversal for the tree

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

After getting the arrays from T1 and T2, merge two sorted array

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

Now, we use the merged sorted array to transfer into balanced BST

def sorted_arr_to_bst(arr):
     
    if not arr:
        return None
 
    # find middle and make it the root
    mid = (len(arr)) // 2
    root = Node(arr[mid])
     
    # left subtree of root
    root.left = sorted_arr_to_bst(arr[:mid])
     
    # right subtree of root
    root.right = sorted_arr_to_bst(arr[mid+1:])
    return root

result

# Inserting values in first tree
    root1 = insert(root1, 100)
    root1 = insert(root1, 50)
    root1 = insert(root1, 300)
    root1 = insert(root1, 20)
    root1 = insert(root1, 70)
     
    # Inserting values in second tree
    root2 = insert(root2, 80)
    root2 = insert(root2, 40)
    root2 = insert(root2, 120)
    arr1 = []
    inorder(root1, arr1)
    arr2 = []
    inorder(root2, arr2)
    arr = merge_sorted_arr(arr1, arr2)
    root = sorted_arr_to_bst(arr)
    res = []
    inorder(root, res)
    print('Following is Inorder traversal of the merged tree')
    for i in res:
      print(i)

Time Complexity: O(m+n)

• Do inorder traversal of the first tree and store into one array takes O(m) time.
• Do inorder traversal of the second tree and store into another array takes O(n) time.
• Merge the two sorted arrays into one array of size m + n takes O(m+n) time.
• The function sorted_arr_to_bst for size m + n array also takes O(m+n) time.

Extra Tips

Get the size of the tree

def size(node):
    if node is None:
        return 0
    else:
        return (size(node.left)+ 1 + size(node.right))

REFERENCE
https://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/
https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
https://www.geeksforgeeks.org/write-a-c-program-to-calculate-size-of-a-tree/