Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node III. A max-heap can be constructed from a binary search tree in Θ(n) time IV. A binary search tree can be constructed from a max-heap in Θ(n) time Which of the above statements are TRUE?

Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node III. A max-heap can be constructed from a binary search tree in Θ(n) time IV. A binary search tree can be constructed from a max-heap in Θ(n) time Which of the above statements are TRUE? Correct Answer I, II and III

Max-heap:

[ alt="GATE CS 112 7Q GATE 2019 images raju D 3" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%203.PNG">

  • Smallest element (12) of the max heap is always at the leaf.
  • Second largest element (25) in a max heap is always a child of the root node


Binary Search Tree:

[ alt="GATE CS 112 7Q GATE 2019 images raju D 4" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%204.PNG">

 

INORDER: 14, 15, 18, 20, 22, 23, 25, 30

Traversal time complexity = O(n)

Store the element in an array in reverse order

Index

0

1

2

3

4

5

6

7

Array elements

30

25

23

22

20

18

15

14

 

Filling the array in reverse order. Time complexity = Θ(n)

Total time complexity = Θ(n) + Θ(n) = Θ(n)

MAX heap:

[ alt="GATE CS 112 7Q GATE 2019 images raju D 5" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%205.PNG">

Statement I, II and III are correct

Important Points:

A binary search tree can be constructed from a max heap in Θ(n2) time

Assume that distinct elements are present

Related Questions

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
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?
Three statements are followed by four conclusions numbered I, II, III and IV. You have to consider these statements to be true, even if they seem to be at variance with commonly known facts, decide which of the given conclusions logically follow(s) from the statements. Statements: 1. No plant is a flower. 2. No flower is a leaf. 3. Some plants are leaf. Conclusions: I. No leaf is a plant. II. No leaf is a flower. III. Some flowers are plants. IV. All leaf are plants.
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 
Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Which of the following is correct for the full binary tree?
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the near node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.
For a tree with just one node, the root node, the height of a binary tree is defined to be zero; if there are 2 levels of nodes, the height is 1 and so on. Binary search tree is built according to the usual rules with the following six keys, inserted one at a time given: B, I, N, A, R, Y. what is the height of the tree?  
In a dicot pot herb, vaseline/vegetable oil was applied on the upper surface of one leaf (Experimental leaf 1) and on the lower surface of another leaf (Experimental leaf 2). Vaseline/Vegetable oil was not applied to the control leaf. The plant was deliberately not watered for several days. Which leaf will dry up last?
Consider the following statements regarding the complete incidence matrix (A) of order n × b (a) The elements aij of A = 1, if branch j is associated with node i and orientation is towards node i (b) The element aij of A = -1, if the branch j is the cut set i and the orientation coincide (c) The element aij of A = 1­, if the branch j is associated with node i and orientation is away from node i (d) The element aij of A = 0, if the branch j is not associated with node i Which of the above statements are correct?
If we implement heap as min-heap, deleting root node (value 1)from the heap. What would be the value of root node after second iteration if leaf node (value 100) is chosen to replace the root at start.