# 1305. All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

# Solution

Approach 1: in order traversal to get sorted values, then merge two sorted lists.

# Code (Python)

Approach 1:

    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        list1, list2 = self.inorder(root1), self.inorder(root2)
        result = []
        p1, p2 = 0, 0
        while p1 < len(list1) and p2 < len(list2):
            if list1[p1] <= list2[p2]:
                result.append(list1[p1])
                p1 += 1
            else:
                result.append(list2[p2])
                p2 += 1
        while p1 < len(list1):
            result.append(list1[p1])
            p1 += 1
        while p2 < len(list2):
            result.append(list2[p2])
            p2 += 1
        return result
    
    def inorder(self, root):
        result = []
        node = root
        stack = []
        while node:
            stack.append(node)
            node = node.left
        while stack:
            node = stack.pop()
            result.append(node.val)
            node = node.right
            while node:
                stack.append(node)
                node = node.left
        return result

# Code (C++)

Approach 1:

Approach 2: