Merging two binary search trees with lowest possible time complexity

Question

I'm currently working on a problem that is completing a function to merge two binary search trees and return a sorted array consisting of all node values of both trees.

I have written a code that works properly but the problem is that it seems its time complexity is not low enough.

The time complexity should be O(M+N) where M and N are the sizes of two binary search trees

And the expected auxilary space shoud be O(Height of BST1 + Height of BST2 + M + N(for storing the answer))

This is the code that I've written

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def inorder_list(theroot):
    l = []
    def inorder(root):
        if root:
            inorder(root.left)
            l.append(root.data)
            inorder(root.right)
    inorder(theroot)
    return l

def merge_two_sorted_lists(list1, list2):
    res = []
    while list1 and list2:
        if list1[0] <= list2[0]:
            res.append(list1.pop(0))
        else:
            res.append(list2.pop(0))
    res += list1
    res += list2
    return res

class Solution:
    
    #Function to return a list of integers denoting the node 
    #values of both the BST in a sorted order.
    def merge(self, root1, root2):
        #code here.
        root1_list = inorder_list(root1)
        root2_list = inorder_list(root2)
        return merge_two_sorted_lists(root1_list, root2_list)

The function inorder_list returns a list cosists of all node values of list (sorted because its inorder traversal)

And the function merge_two_sorted_lists merges two sorted lists and returns a sorted list consist of all elements of both lists.

The time complexity of every inorder traversal function is O(size of the bst) and the time complexity of merge_*two_*sorted_lists is the size of the first list + the size of the second list (M+N).

My idea to create an empty stack and filling it while traversing both BTSs simultaneously but i don't know how to do it .

Is there any other algorithm that its time complexity is O(M+N)?

Answer 1

Your merge_two_sorted_lists isn't O(M+N), due to the costly pop(0). Just do return sorted(list1 + list2).

Python's sorted recognizes the two sorted runs and merges them in linear time (at least in CPython, which you're most likely using, and apparently also in PyPy). Alternatively, use list(heapq.merge(list1, list2)) or use deques and .popleft(), or any other way to merge in linear time.

How I might do it:

class Solution:
    def merge(self, root1, root2):
        data = []
        def inorder(root):
            if root:
                inorder(root.left)
                data.append(root.data)
                inorder(root.right)
        inorder(root1)
        inorder(root2)
        data.sort()
        return data