Two balanced binary trees are given with m and n elements, respectively. They…
2021
Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.
- A.
\(O(m*n)\) - B.
\(O(m+n)\) - C.
\(O(m*log n)\) - D.
\(O(m*log(m+n))\)
Attempted by 457 students.
Show answer & explanation
Correct answer: B
Answer: O(m+n)
Reasoning and algorithm:
Do an inorder traversal of the first balanced BST to produce a sorted array of its m elements. This takes O(m) time.
Do an inorder traversal of the second balanced BST to produce a sorted array of its n elements. This takes O(n) time.
Merge the two sorted arrays into a single sorted array of size m+n. This merge step takes O(m+n) time.
Build a balanced binary search tree from the merged sorted array by recursively choosing midpoints as roots. This also runs in O(m+n) time.
Complexity: Summing the costs gives O(m) + O(n) + O(m+n) + O(m+n) = O(m+n).
Note: Methods that insert elements one-by-one into the other tree lead to higher costs (for example, repeated insertions would incur logarithmic factors) and are therefore suboptimal compared to the linear merge approach.
A video solution is available for this question — log in and enroll to watch it.