Bissoy.com
Doctors Medicines MCQs Q&A

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

Two balanced binary trees are given with m and n elements respectively. They can be merged into a balanced binary search tree in ____ time. Correct Answer O(m+n)

First we store the in-order traversals of both the trees in two separate arrays and then we can merge these sorted sequences in O(m+n) time. And then we construct the balanced tree from this final sorted array.

Related Questions

We create a binary search tree B1 by inserting the numbers 1, 2, 3, 4, 5 into an empty binary search tree. We create another binary search tree B2 by inserting the numbers into an empty binary search tree in the reverse order. What is the difference between the right-most element of B1 and the left-most element of B2?
Which of the following is/are correct about a strictly binary tree? A. A binary tree is called strictly binary tree if every non-­leaf node of it has non empty left and right sub tree B. In strictly binary tree can have two children or no child C. A strictly binary tree with n leaves always contact 2n­-1 nodes
Consider the following two sets of LR(1) items of an LR(1) grammar. X → c.X, c/d           X → c.X, $ X → .cX, c/d           X → .cX, $ X → .x, c/d             X → .d, $ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.
In the following question, there are six parts marked S1, S6, P, Q, R and S. The position of S1 and S6 are fixed. Some parts of the sentence have been jumbled up. Rearrange these parts and choose the proper sequence from the given options. (S1) Once upon a time, there lived a farmer in a village, beside a forest. (P) When the farmer was a little boy, he spent much of his time playing with the apple tree (Q) Those days, the apple tree had given the choicest of apples to him (R) However, as time passed, the apple tree became old and stopped bearing fruits (S) He had a big garden that had an old apple tree and other plants, trees and beautiful flowers (S6) Now that the farmer was not getting any apples from the tree, he decided that the tree was useless and cut it.
In the following question, there are six parts marked S1, S6, P, Q, R and S.The position of S1 and S6 are fixed. Some parts of the sentence have been jumbled up. Rearrange these parts and choose the proper sequence from the given options. (S1) Once upon a time, there lived a farmer in a village, beside a forest. (P) When the farmer was a little boy, he spent much of his time playing with the apple tree (Q)Those days, the apple tree had given the choicest of apples to him (R) However, as time passed, the apple tree became old and stopped bearing fruits (S)He had a big garden that had an old apple tree and other plants, trees and beautiful flowers (S6) Now that the farmer was not getting any apples from the tree, he decided that the tree was useless and cut it.
There is a statement followed by two conclusions. Decide which conclusion logically follows from the given statement (s). Statement: A garden has mango, teak, neem, orange, coconut and many trees. The mango tree is 7 meters tall, the orange tree is half of its height and the coconut tree is three times the height of the mango tree. Conclusion: I. The average height of the three trees is less than 10 meters. II. The tallest tree in the garden is the coconut tree. Choose the correct option from the following. A. Only (I) follows. B. Only (II) follows. C. (I) and (II) both follow. D. Neither (I) nor (II) follows.
One-sixth of the trees in a garden are neem trees. Half of the trees are Ashoka trees and the remaining are eucalyptus trees. If the number of neem trees is five, then how many eucalyptus trees are there in the garden?
One-sixth of the trees in a garden are jamun trees, half of the trees are Eucalyptus trees and the remaining are peepal trees.  If the number of jamun trees is 6, how many peepal tree are there in the garden? 
Consider the following two C code segment. Y and X are one- and two-dimensional arrays of size n and n × n respectively, where 2 ≤ n ≤ 10. Assume that in both code segments, elements of y are initialized to 0 and each element X[i] [j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of x are in same main memory page frame. Code segment 1:                 //initialize elements of y to 0                 //initialize elements X[i] [j] of X to i+j                       for (i = 0; i < n; i++)                                 Y[i] += X[0] [i]; Code Segment 2:                 //initialize elements of Y to 0                 //initialize elements X[i] [j] of X to i+j                        for (i = 0; i < n; i++)                                 Y[i] += X[i] [0]; Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode {              treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) {              int value=0;              if (tree != NULL) {              if (tree->leftMostChild == NULL)              value = 1;    else               value = DoSomething(tree->leftMostChild);               value = value + DoSomething(tree->rightSibling);     }               return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the