Problem 1 [15 points]: In a binary search tree, recall that the successor a node N with two children is found at the left-most node in the subtree rooted at the right child of N (i.e., the node found by starting at Ns right child, and then traversing left-child links until the current node does not have a left child). Now instead, consider a node N with no right child. Give an algorithm (either in English or in pseudo-code) that returns the successor of such a node N (or returns null if N contains the maximum value in the entire tree).

Problem 2 [5 points] Suppose we are given an array A in sorted order. Using the scheme discussed in class for implementing a heap, does A constitute a valid min-heap? Briefly justify your answer.

Problem 3 [20 points]: Suppose we are given k ArrayLists L1, L2, . . ., Lk, which collectively contain n integers (i.e., L1.size() + L2.size() + . . . + Lk.size() = n); furthermore, assume each list is already given in sorted order. Give an O(n log k)-time algorithm (either in English or in pseudo-code) that merges the k sorted lists into a single sorted list containing all the integers. Briefly justify the correctness of your algorithm and why it achieves a run-time of O(n log k). (Hint: Use a min-heap.)