Create a binary search tree from a list of numbers sorted in increasing order

gistfile1.txt

//Precondition: A is a list of elements, sorted in increasing order
//              P is the root of the binary tree to be created

//Postcondition: P is the root of a binary tree containing all elements in A

procedure mktree(list A, node P)
  if A is empty,
    return

  middle = A.length/2
  rightSubList = A.getElementsRightOf(middle)
  leftSubList = A.getElementsLeftOf(middle)

  P = A[middle]

  mktree(leftSubList, P.leftChild() )
  mktree(rightSubList, P.rightChild() )



//===========================================================================
Recurrence: T(n) = 2T(n/2) + 1

Solving via recursion tree method yields: summation from k=1 to log(n) of 2^k, which = 2^(logn+1) -1 which is O(n)