All_Elements_In_Two_Binary_Search_Trees.py

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].


# 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



# O(n) Time and O(n) Space
class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        
        def inorder_traversal(node):
            if not node:
                return []
            
            return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)
        
        tree_1 = inorder_traversal(root1)
        tree_2 = inorder_traversal(root2)
        
        n_1, n_2 = len(tree_1), len(tree_2)
        ptr_1, ptr_2 = 0, 0
        result = []
        while ptr_1<n_1 or ptr_2<n_2:
            
            if ptr_2==n_2 or (ptr_1 < n_1 and tree_1[ptr_1] <= tree_2[ptr_2]):
                result.append(tree_1[ptr_1])
                ptr_1 += 1
                
            elif ptr_2<n_2:
                result.append(tree_2[ptr_2])
                ptr_2 += 1
                
        return result

# O(nlogn) Time and O(n) Space
class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        
        def inorder_traversal(node):
            if not node:
                return []
            
            return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)
        
        tree_1 = inorder_traversal(root1)
        tree_2 = inorder_traversal(root2)
        
        return sorted(tree_1 + tree_2)