16 views

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. asked in Others | 16 views ## 1 Answer 0 votes 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.