Is it possible to merge two trees that satisfy the heap order in time O(m n 1)? While m and n are the height of the input trees.

Example 

Input:
   10              8
     \
      9 
Output: (Can be any one of them)
   10               10             10          10
     \             /  \           /  \        /  
      9           9    8         8    9      9
     /                                      /
    8                                      8

CodePudding user response：

Yes, this can be done in O(