'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


# 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 getAllElements2(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        stack1, stack2, output = [], [], []
        
        while root1 or root2 or stack1 or stack2:
            # update both stacks
            # by going left till possible
            while root1:
                stack1.append(root1)
                root1 = root1.left
            while root2:
                stack2.append(root2)
                root2 = root2.left

            # Add the smallest value into output,
            # pop it from the stack,
            # and then do one step right
            if (not stack2) or (stack1 and stack1[-1].val <= stack2[-1].val):
                root1 = stack1.pop()
                output.append(root1.val)
                root1 = root1.right
            else: # not stack1 or stack2 and stack1[-1].val >= stack2[-1].val:
                root2 = stack2.pop()
                output.append(root2.val)   
                root2 = root2.right

        return output
    
    
    # self-made; T: O((M+N)log(M+N))
    # S: O(M+N)
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        res1 = []; self.helper(root1, res1)
        res2 = []; self.helper(root2, res2)
        res = res1 + res2
        res.sort()
        return res
        
        
    def helper(self, root, res):
        if not root:
            return
        if root:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)
        return res
    
    # a shorter inorder function
    def getAllElements1(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        def inorder(r: TreeNode):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        return sorted(inorder(root1) + inorder(root2))