Binary Search Tree. a) Beginning with an empty binary search tree, insert the following key values one by one and show the resulting binary search tree T after all insertions (i.e. show only the final tree). 1, 3, 5, 7, 9, 2, 4, 6, 8. b) Show the resulting tree after the node with key 3 is deleted from the binary search tree T from Part (a). c) Consider the operation of a right rotation on a binary search tree T on the nodes x and y. After the rotation, x becomes the parent of y. i) Initially, let the left and right subtrees under x be alpha and beta, respectively, and let the right subtree under y be gamma. Draw the diagram of the subtree of T rooted at y before the right rotation, and the subtree rooted at x after the right rotation. ii) The attributes of a node x are x.key, x.left, x.right, x.p. Assume that subtrees alpha, beta, and gamma are not empty and y is not the root of T. Complete the pseudocode below for right-rotate RIGHT-ROTATE(T, y) x = y.left y.left = x.right x.right.p = y x.p = y.p if y == y.p.left