a) Suppose that we insert an element y into a non-empty binary search tree that does not already contain y. Then we immediately delete it from the tree. Will the tree after deletion be identical to the original one? Justify your answer with no more than 5 sentences. Draw pictures if necessary.

b)Consider the following algorithm to find the smallest item in a list of n distinct integers:

1. Pick an element, x, from the list at random.

2. Go through every other element in the list. If an element is less than x put it in list 1, and if it's more than x, put it in list 2. (Note: Since all elements in the list are distinct, none will equal to x.)

3. If list 1 is empty, then return x, since it's the smallest element. If list 1 is NOT empty, go back to the first step, only using list 1. In terms of n, what is the best case run-time of this algorithm? In terms of n, what is the worst case run-time of this algorithm? Justify both answers in words.