Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.

1. AO(m*n)
2. BO(m + n)
3. CO(m*log n)
4. DO(m*log(m + n))

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. O(m + n)

Explanation

Inorder-traverse both trees into sorted arrays (O(m + n)), merge them (O(m + n)), and build a balanced BST from the merged array (O(m + n)).