1. Write a function to generate the AVL tree of height h with fewest nodes. What is the running time of your function?
2. Write a function to generate a perfectly balanced binary search tree of height h with keys 1 through 2h+1 - 1. What is the running time of your function?
3. Write a function that takes as input a binary search tree, T, and two keys, k1 and k2, which are ordered so that k1 ≤ k2, and prints all elements X in the tree such that k1 ≤ Key(X) ≤ k2. Do not assume any information about the type of keys except that they can be ordered (consistently). Your program should run in O(K + log N) average time, where K is the number of keys printed. Bound the running time of your algorithm.