2 Written Question 2 (25 marks) A binary tree is ideally weight balanced if, for every node x in the tree, the number of nodes in its two subtrees differs by at most 1. 1. (10 marks) Give an algorithm with worst case running time in O(n) that, given a sorted array of n elements, constructs an ideally weight balanced binary search tree. Briefly justify the correctness of your algorithm and why it runs in O(n) time in the worst case. 2. (10 marks) Give an algorithm which has a worst case running time in O(n) that, given an n node binary search tree, transforms it into an ideally weight balanced binary search tree for the same elements. Briefly justify the correctness of your algorithm and why it runs in O(n) time in the worst case. 3. (5 marks) Prove that there is no O(n) time comparison based algorithm that, given an unsorted array of n elements, constructs an ideally balanced binary search tree