Given two binary search trees with root nodes as bst1 and bst2 of size n and m, write a program to return an array of integers that contains all the elements of bst1 and bst2 in non-decreasing order.

Problem Note

  • The expected time complexity is O(m+n).

Example 1

Input:      3            4        
           / \          / \
          2   5        1   6
Output: [1, 2, 3, 4, 5, 6]
Explanation: The resultant binary tree contains all the elements of bst1 and bst2 in non-decreasing order.

Example 2

Input:      3            6        
             \          / \
              4        2  10
Output:[2, 3, 4, 6, 10]
Explanation: Both bst1 and bst2 are combined to return the BST having all the elements of bst1 and bst2 in non-decreasing order.