# 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: