class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        one = self.traverse(root1)
        two = self.traverse(root2)
        
        temp = one + (len(two) * [0])
        
        self.merge(temp, len(one), two, len(two))
   
        return temp
        
    # [1,2,4,0,0,0]
    # [0,1,3]
    def merge(self, nums1, m, nums2, n):
        k = len(nums1) - 1
        m = m - 1
        n = n - 1
        
        while m >= 0 and n >= 0:
            if nums1[m] > nums2[n]:
                nums1[k] = nums1[m]
                k -= 1
                m -= 1
            else:
                nums1[k] = nums2[n]
                k -= 1
                n -= 1
        
        while n >= 0:
            nums1[k] = nums2[n]
            k -= 1
            n -= 1
        
        return nums1
    
    def traverse(self, root):
        output = []
        
        def helper(node):
            if not node:
                return
            helper(node.left)
            output.append(node.val)
            helper(node.right)
        
        helper(root)
        return output