Problem 1 (15 points, 5 points each part): The following is the pseudo-code for a left rotation about a node in a binary search tree // Input: T, a bi nary search tree: this tree is mani pul ated in place // Input: X, a node of T // Output: The same bi nary search tree, T, after a left rotation about the node x Left Rot at e( T, x) // Save a copy of the right child of x y -X.right // Move y's left sub-tree to be x's right sub-tree x. right - y. I eft // Check if this new sub-tree was 0. If not, set its par ent to be x if x. right # X.right. parent - X // After the rotation, y's parent will be the current par ent of x. // Set this relat i onship now. y. par ent - X.parent // Check if x is the root. If so, the new root will be y. if x = Root [T] Root[T] - y el se // x was not the root. We need to update the child pointers of x's parent. // Check if it is a left or right child. if x = x. parent.left X.parent. I eft - y el se x.parent.right - y // After the rotation, x will become the left-child of y y. I eft X. par enty a) Give the pseudo-code for a right rotation. b) Fill in the keys in the nodes of the tree shown below with the values 1 to 19 such that the result is a binary search tree. Hint: where must the 1 go? For the remaining nodes, use the Tree Successor algorithm described in class. c) For the resulting tree, show the effect of a left rotation about 12 followed by a right rotation about 6