CareerCup

Recursive version.

/// right is one past the array.
/// Creates a tree of array[left,..., right-1].
Tree * CreateTree(int *array, int left, int right) {
  
    if (left >= right) throw InternalErrorException("...");
    if (left == right-1) return new Tree(array[left]);
   
    mid = (right - left)/2 + left;
  
    Tree *tree = new Tree(array[mid]);
    tree->Left = CreateTree(array, left, mid);
    tree->Right = CreateTree(array, mid+1, right);
    return tree;
}

# In Python a simple way to represent a binary
# tree is as a tuple: (left_tree, val, right_tree)
def create_tree(lst):
    def _maketree(low, high):
        # Making a balanced tree is simply a matter
        # of taking the middle value as the root
        # and recursively building the subtrees
        # on the left and right.
        if low > high:
            return None
        if low == high:
            return (None, lst[low], None)
        mid = (low + high) / 2
        val = lst[mid]
        left = _maketree(low, mid - 1)
        right = _maketree(mid + 1, high)
        return (left, val, right)
    return _maketree(0, len(lst) - 1)

def traverse(tree):
    if tree is None:
        return
    left, val, right = tree
    traverse(left)
    print val
    traverse(right)

def tree_height(tree):
    if tree is None:
        return 0
    left, val, right = tree
    lh = tree_height(left)
    rh = tree_height(right)
    return max([lh, rh]) + 1

lst = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
tree = create_tree(lst)
print tree
assert 4 == tree_height(tree)
traverse(tree)

hi,
as per the question, if you have sorted array, and want to make binary tree with minimun height then you should build a BST with the middle value of array as the root. do this recuirsively, so that it will be a kind of balance tree and height will be minimal.

Should not you compute
mid = (left + right) / 2

BinaryTree* sortedArrayToBST(int arr[], int start, int end) {
if (start > end) return NULL;
int mid = (start + start) / 2;
BinaryTree *node = new BinaryTree(arr[mid]);
node->left = sortedArrayToBST(arr, start, mid-1);
node->right = sortedArrayToBST(arr, mid+1, end);
return node;
}

BinaryTree* sortedArrayToBST(int arr[], int n) {
return sortedArrayToBST(arr, 0, n-1);
}

#include <stdio.h>
#include <stdlib.h>

struct node
{
	int value;
	struct node* left;
	struct node* right;
};


struct node* constructBST(int*,int,int);
void printTree(struct node*);

void main()
{

	int array[10] = {1,2,3,4,5,6,7,8,9,10};
	int start = 0;
	int end = 9;
	
	struct node *head;

	head = constructBST(array, start, end);

	printTree(head);

	return;
}


struct node* constructBST(int *array, int start, int end)
{
	int size = end - start + 1;

	if(size == 1)
	{
		struct node *nd;
		nd = (struct node*)malloc(sizeof(struct node));
		nd->value = array[start];
		nd->left = NULL;
		nd->right = NULL;
	
		return nd;

	}else if(size == 0)
	{
		return NULL;
	}else{

		int median = (start + end)/2;
		struct node *nd;
		nd = (struct node*)malloc(sizeof(struct node));
		nd->value = array[median];
	
		nd->left = constructBST(array, start, median-1);
		nd->right = constructBST(array, median+1, end);

		return nd;
	}

} 
	

void printTree(struct node *head)
{
	struct node *curr = head;

	if(curr == NULL)
		return;

	printTree(curr->left);
	printf("%d->", curr->value);
	printTree(curr->right);

}

easy.jst take middle element as the current node and make it the tree node then divide tree in two sub array and do recursivly.

struct Node *CreateTree(int arr[],int start,int end)
{
if(start>end)
return NULL;
int mid=(start+end)/2;
struct Node *node=NewNode(arr[mid]);
node->left=CreateTree(arr,start,mid-1);
node->right=CreateTree(arr,mid+1,end);
return node;
}

TreeNode* CreateTree(TreeNode *root, int *arr, int l, int r)
{
if(l == r + 1 || r == l -1)
return NULL;
else
{
int mid = (l + r) / 2;
root = new TreeNode();
root->data = arr[mid];
root->left = CreateTree(root, arr, l, mid-1);
root->right = CreateTree(root, arr, mid+1, r);
}
return root;
}

wheelsfortomorrow.wordpress.com/2013/02/20/creating-minimal-height-binary-tree-using-a-sorted-array/