Constructing Balanced Binary Search Trees

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 TreeNode that includes instance variables key, left, and right.

(a) Write pseudocode (or Java code if you wish) for an algorithm that constructs the tree and returns the root node. (If using Java don't worry about making the enclosing BinaryTree

class instance.) 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?