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

Leave a Reply

Your email address will not be published.