[Leet Code] All Elements in Two Binary Search Trees

Leetcode: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

Problem:

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

Solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getAllElements(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: List[int]
        """
        elements = []
        self.traverse(root1, elements)
        self.traverse(root2, elements)
        return sorted(elements)
        
    def traverse(self, root, elements):
        if root:
            self.traverse(root.left, elements)
            elements.append(root.val)
            self.traverse(root.right, elements)

Explanation:

This is quite a simple one actually, even though it’s labelled as a medium. All we have to do is create a helper method to traverse the tree in-order, then we call that twice with the elements array that we define in order to put our values that are found in the tree in there. Then lastly, we call the native sorted method on the list of elements, and this will provide us with the answer.