https://leetcode.com/problems/all-elements-in-two-binary-search-trees

Pretty easy problem in my opinion: because the first idea which you usually think when you see this problem will work. So, what we need to do?

  1. Traverse each tree, using inorder traversal, in this way for BST result will be sorted list.
  2. Now, we have two sorted lists, and all we need to do is to merge them, using the same routine we use in merge sort.

Complexity: time complexity is O(n1) for first BST, where n1 is number of nodes and O(n2) for the second tree. Then we need to merge and we do it in n1+n2 time, so overall time complexity is O(n1+n2). Space complexity is also O(n1+n2). I think space can be improved a bit, if we somehow directly merge values from both trees in the same list.

class Solution:
    def getAllElements(self, root1, root2):
        def inorder(root, lst):
            if not root: return
            inorder(root.left, lst)
            lst.append(root.val)
            inorder(root.right, lst)
        
        lst1, lst2 = [], []
        inorder(root1, lst1)
        inorder(root2, lst2)
        
        i1, i2, res = 0, 0, []
        s1, s2 = len(lst1), len(lst2)
        
        while i1 < s1 and i2 < s2:
            if lst1[i1] < lst2[i2]:
                res += [lst1[i1]]
                i1 += 1
            else:
                res += [lst2[i2]]
                i2 += 1
                
        return res + lst1[i1:] + lst2[i2:]

If you like the solution, you can upvote it on leetcode discussion section: Problem 1305