1. [10 Suppose that we want to generate a BST by inserting the keys 1 through n into an initially empty BST (assume n 1). Assume that the insert sequence is a random permutation of [1,2,3,... ,n] and each permutation is equally likely to occur. Answer the following questions. (a) What is the maximum possible height of the generated BST? Describe three different insert sequences that would result in a BST with the maximum height. (b) By picking a random permutation of [1,2,3,...,r as the insert sequence, what is the probability that the resulting BST has the maximum height? Show detailed steps of your calculation with clear justification