Inserting a new value in binary search tree

Question

Using an algorithm Tree-Insert(T, v) that inserts a new value v into a binary search tree T, the following algorithm grows a binary search tree by repeatedly inserting each value in a given section of an array into the tree:

Tree-Grow(A, first, last, T)
1 for i ← first to last
2 do Tree-Insert(T, A[i])


1. If the tree is initially empty, and the length of array section (i.e., last-first+1) is n, what are the best-case and the worst-case asymptotic running time of the above algorithm, respectively?

2. When n = 7, give a best-case instance (as an array containing digits 1 to 7, in certain order), and a worst-case instance (in the same form) of the algorithm.

3. If the array is sorted and all the values are distinct, find a way to modify Tree-Grow, so that it will always build the shortest tree.

4. What are the best-case and the worst-case asymptotic running time of the modified algorithm, respectively?