Problems to be handed in. Please submit each problem on a separate sheet of paper. Give algorithms for implementing the following operations on a binary search tree:
(a) Average-Keys: Given a node x, returns the average value of the keys in the subtree rooted at x. For full credit your procedure should run in O(n) time.
(b) Range Search: Given an interval [a, b] and a tree T, returns a list of all the nodes with keys in the range a, b. There is an easy theta (n) solution, but for credit your algorithm should run in time O(k + h) where k is the number of nodes in the range and h is the height of the search tree.
Analyze the running time of your algorithm carefully. Remember that some of the homework grade is for the clarity of your explanation.