Sorted Array to Binary Tree

Given a sorted (non-decreasing order) array, write an algorithm to
create a binary tree with minimal height. Do this in O(n).

Answer:

The trick is to add the mid element of the array first, because if the elements are sequentially , then the tree will resemble a linked list.

Node* CreateTree(int* array, size_t begin, size_t end)
{
  if( begin > end )
   return NULL;
  size_t mid = (begin+end) / 2;
  Node* n = CreateNode(array[mid]);
  n->left = CreateTree( array, begin, mid-1 );
  n->right = CreateTree( array, mid+1, end );
  return n;
}