ISI2016-PCB-CS-1

Question

1. Consider the array $A=[20,13,19,8,3,5,4]$ that represents a heap. Draw the heap after removing the element $20.$
2. List all the distinct integer keys $k$ such that, when $k$ is inserted in the Binary Search Tree of Figure $1,$ its height increases. Note that you are not allowed to insert an already existing key again. Justify your answer.

Comments

I) [ 19 13 5 8 3 4 ]

Answer 1

I. Am assuming we have to make max heap.

For the given array heap will have is

Swap 20 and 4

Delete 20 which is leaf now than Max heapify.

19 > 4 so swap

5 > 4 so swap

Images made using: http://btv.melezinek.cz/binary-heap.html

II. Answer is 38.

We have to add one new key k such that height of the tree increases. To increase height additions should be at the last level.

Let's see the cases.

For K < 37, no increase in height as we will be adding k as left child of 37.

For  K = 37 duplicates not possible

For K =38, it will be added as left child of node 39 (last level node) so height increases.

For  K = 39 or 40 duplicates not possible

For  K = 41 will be added as left child of node 42, no increase in height.

For $42  < K < 95 $ Will be added as right child of 42 (not last level node) so no increase on height.

For $ 95< K < 111$ Will be added as left child of 111  (not last level node) so no increase on height.

For  K = 111 or 112 or 113, duplicates not possible

For  113 < K < 125, Will be added as left child of 125 (not last level node) so no increase on height.

For  K > 125, Will be added as right child of 125 (not last level node) so no increase on height.