GATE Overflow Test Series | Data Structures | Test 1 | Question: 15

Question

Two balanced binary search trees are given with $m$ and $n$ elements respectively. They can be merged into another balanced binary search tree in $\Theta((m+n)^a {(\log (m+n))}^b)$ time. $2.a + 3b =$ _____

Comments

“By doing an inorder traversal of the given BSTs, we can get the inorder of the merged BST”.Are we doing like this:

1)Do inorder of BST1 (we get sorted array m)

2)Do inorder of BST2 (we get sorted array n)

3)Create new array of size m+n.Fill it using merge procedure in O(m+n)

time=O(m)+O(n)+O(m+n)

 

Answer 1

By doing an inorder traversal of the given BSTs, we can get the inorder of the merged BST in $O(m)+O(n) = O(m+n).$ Once we have the inorder of the merged BST, we can construct this tree as follows.

1. Make the middle element the root
2. Make the middle of the left subarray as the left child
3. Make the middle of the right subarray as the right child
4. Recursively do steps 1-3 until all elements of array are processed

Time complexity of above $=O(m+n)$ as no element is processed more than once.

Thus we get $a = 1, b = 0.$

Correct Answer $=2\times 1 = 2.$