We want to construct a Binary Search Tree by inserting the keys 1 to k into an empty Binary Search Tree (assume k > 1). Suppose that the insertion pattern is a randomized permutation of [1, 2, 3, 4 . . , k] with equal probability.

(i) What is the maximum possible height of it? Describe four different insertion patterns that result in maximum height.

(ii) By picking a randomized permutation of [1, 2, 3, 4. . . , k] as the insertion pattern, what is the probability that the resulting maximum height? Show steps and calculation