CSE 214 Computer Science II (Spring 2015)

RECITATION 11 – Heap and Binary Search Tree

Objective:

1. To study Heap and its operations
2. To study Binary Search Tree

1. [10 min] The following elements are inserted one by one in the given order into a heap. Draw the resulting Min Heap

            (22, 15, 36, 44, 10, 3, 9, 13, 29, 25).

                         a. Show the insertion of  elements 5 and 16  in min heap

                        b. Show the deletion of elements 3  and 25 from min heap

2. [10 min]  Draw the heap for the following scenario

                a. Bill claims that a preorder traversal of a heap will list its keys in nondecreasing order. Draw an

                  example of a heap that proves him wrong.

               b. Hillary claims that a postorder traversal of a heap will list its keys in nonincreasing order. Draw an

                  example of a heap that proves her wrong.

3. [10 min] Answer the following

                   a. How could you sort a list of n random numbers using a heap? What would the time complexity be?

                   b. What is the complexity for insertion of element into the Binary Search Tree?

                   c. What is the complexity for deleting an element from the Binary Search Tree?

4. [10 min] Insert, into an empty binary search tree, entries with keys 30, 40, 24, 58, 48, 26, 11, 13 (in this order). Show the construction step by step

                      a. Show the insertion of elements 29, 27 and 55  into binary search tree.

                      b. Show the deletion elements 24, 40 and 58  from binary search tree

      5. [5 min] Justify the following scenario

           Dr. Amongus claims that the order in which a fixed set of entries is inserted into a binary search tree does

           not matter—the same tree results every time. Give a small example that proves he is wrong.

6. [5 min] Carry out the following deletion operation in sequence on Binary Search tree with elements : 17,13,21,10,15,24,4,11,16,23,27,25,26

1. Delete 4   (b) delete 10  (c) delete 27  and (d) delete 13