LeetCode 1305. All Elements in Two Binary Search Trees

Description

https://leetcode.com/problems/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]
```

Constraints:

• Each tree has at most `5000` nodes.
• Each node’s value is between `[-10^5, 10^5]`.

Explanation

Use in order traverse on both trees to get two ascending order lists. Then merge two lists into one ascending order list.

Python Solution

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:

results1 = []
self.inorder_traverse(root1, results1)

results2 = []
self.inorder_traverse(root2, results2)

results = []

i = 0
j = 0

while i < len(results1) and j < len(results2):
if results1[i] < results2[j]:
results.append(results1[i])
i += 1
else:
results.append(results2[j])
j += 1

while i < len(results1):
results.append(results1[i])
i += 1

while j < len(results2):
results.append(results2[j])
j += 1

return results

def inorder_traverse(self, root, results):
if not root:
return

self.inorder_traverse(root.left, results)
results.append(root.val)
self.inorder_traverse(root.right, results)
``````
• Time Complexity: O(N).
• Space Complexity: O(N).