I desperately need some help with this problem. I have no idea how to even tackle solving it. Can someone please help? Suppose you have some data keys sorted in an array and you want to construct a balanced binary search tree from them. Assume a tree node representation TreeNodethat includes instance variables key, left, and right.

(a) Write very simple pseudocode for an algorithm that constructs the tree and returns the root node. You will need to use methods for making a new TreeNode, and for setting its left and right children.

Hints: First, identify the array location of the key that would have to be the root of the balanced BST. Now think about how BinarySearch works on the array. Which item does it access first in any given subarray it is called with? Using a similar strategy a simple recursive algorithm is possible.

(b) What is the cost to construct the tree? Justify your answer.

(c) Compare the expected runtime of BinarySearch on the original array to the expected runtime of BST TreeSearch in the tree you just constructed. Have we saved time?