Let S be a sorted array of n integers Give an algorithm that

Let S be a sorted array of n integers. Give an algorithm that constructs a BST of depth O(log n) that stores the elements of the S. Analyze the worst-case run time of your algorithm. Your grade depends on the run time.

Solution

Algorithm

function createBST(array, firstIndex, lastIndex)

Begin

If firstIndex < lastIndex

Begin

Get middleIndex = (firstIndex + lastIndex)/2;

Set root as element on middle index

Set root left tree as createBST(array, firstIndex, lastIndex -1)

Set root right tree as createBST(array, lastIndex+1,lastIndex)

End If

End function