If a binary search tree has items x1 < x2 < ... < xn, define the cost to lookup an item x to be the number of comparisons made in searching for it in the tree (if the item is in the tree, this is always 1 plus the distance between the item and the root). Thus, the cost for looking up the root is 1. In this question we will only ever do lookups for items in the tree.

Given items x1 < x2 < . . . < xn, there are many BSTs that we can build on these numbers. If we have a sequence of requests, we can calculate the total cost of the requests of the different BSTs, and thus we can define an optimal BST for a request sequence.

(b) In the general case, if the optimal BST for a given request sequence has xi at the root, prove that the left subtree must be an optimal BST for the requests on x1,...,xi?1 and the right subtree must be an optimal BST for the requests on xi+1, . . . , xn.

(c) Use the above observation to give a general algorithm for constructing an optimal BST for a given sequence x1 < x2 < ... < xn and their counts c1,...,cn (where ci is the number of times xi is accessed). The running time of your algorithm should be O(n3).