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.