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 N's 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 justily your answer. Problem 3 [20 points: Suppose we are given k ArrayLists L1, L2,..., Lk, which collectively contain n integers (i.e., L1.sizeO + L2.size) + Lk.size );furthermore, as- sume 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 Ik 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