gate 2019

Question

Consider the following statements.

 (i) In max Heap smallest element is at the leaf node.

(ii) In max Heap second largest element always the child of root.

(iii) Binary search tree can be constructed from max heap in θ(n).

(iv) Max Heap can be build from Binary search tree in θ(n)

Which of the above option is correct?

(a) (i), (ii) and (iii)

(b) (i), (ii) and (iv)

(c) (ii), (iii) and (iv)

(d) (i), (iii) and (iv)

Comments

B I think

---

why not a ?

see binary earch tree can be skewed  and for max heap we have to find largest element

---

Let's say there is a heap with level order traversal 9,5,7,4,3,2,6 how will you make bst in linear time

For bst,we can just make an inorder traversal and fill the heap in the reverse order of the traversal

---

https://www.geeksforgeeks.org/convert-bst-to-max-heap/
therefore B?

---

is the option sequence here same as in exam ?

---

I think 3rd option is max heap to bst not bst to max heap

---

this was two marks question?

---

i think options shuffled here..

i think III) was Max heap can be constructed from BST in theta(n)

---

I think questions can be shuffled , options might not :P too much complexity in matching then :P

---

I think 2 can be false what if elements are 9,9,9,7,8,5 then  root's children are not second largest.. correct me if I am wrong

---

You've a point here , then none of the options seem to be completely correct

---

If we could have a method to create a bst in O(n) then we could get sorted order of keys in O(n) thus breaking the lower bound of comparison based sorting.