Hi all,
I was confused what wouldbe the time complexity for the following question

1305. All Elements in Two Binary Search Trees

to solvethis, I used inorder traversal and stored the elements of both the trees in 2 separate lists
Now that I have 2 sorted lists, I used the merge function of merge sort to merge the 2 arrays
Now,
inorder traversal time complexity: O(n) where n = no. of elements in the tree
so considering we have 2 trees and first tree has 'n' elements and second tree has 'm' elements, I am assuming the time complexity for conducting an inorder traversal two times is: O(n+m).

then, given sorted arrays, merge function takes complexity of O(n+m) because n+m = total elements

so, in such a case, what will be my net time complexity?
Inorder traversal twice: O(n+m)
merge function complexity : O(n+m)
adding both of them --> O(n+m) + O(n+m) = O(2(n+m)) = O(n+m)
therefore O(n+m) is the net time complexity. Am I correct?

space compexity question
inorder traversal for first tree (with height h1) ---.> O(h1)

inorder traversal for first tree (with height h1) ---.> O(h2)

now, after inorder traversal we have 2 separate elements to store elements of respective trees. so space complexity here ---.> O(n+m) where n and m are number of elements in tree number one and tree number two respectively.

Now, we have a third array to store the sorted values. Therefore, this third array has size n+m so space complexity ----> O(n+m)

Net space complexity is O(h1) + O(h2) + O(n) + O(m) + O(n+m)
total = O(h1+h2+2(n+m))
total = O(h1+h2+n+m)
now, in the worst case, h1 = n and h2 = m
so, worst case complexity becomes O(n+m+2(n+m) = O(3(n+m) = O(n+m)

NET SPACE COMPLEXITY = O(N+M)
Where n = number of nodes in tree one and m = number of nodes in tree two

please bear with me. Thanks again for taking the effort to read till here!

Here is my code:

def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
    #inorder traversal then merge sort
    
    def inorder(root):
        elements = []
        if root:
            if root.left == None and root.right== None:
                elements+= [root.val]
                return elements

            if root.left:
                elements+=inorder(root.left)

            elements.append(root.val)

            if root.right:
                elements+=inorder(root.right)
        return elements
    
    first = inorder(root1)
    second = inorder(root2)
    final = []
    #merge sort 
    i = 0
    j = 0
    
    while i<len(first) and j<len(second):
        if first[i]<=second[j]:
            final.append(first[i])
            i+=1
        elif second[j]<first[i]:
            final.append(second[j])
            j+=1
            
    while i<len(first):
        final.append(first[i])
        i+=1
    
    while j<len(second):
        final.append(second[j])
        j+=1
    return final