CareerCup

Node makeTree(int a[],int start,int end)
{
	if(start>end)
return null;
//to keep overflow away
int mid=start+(end-start)/2;
Node n=new Node();
n.info=a[mid];
n.left=makeTree(a,start,mid-1);
n.right=makeTree(a,mid+1,end);
return n;


}

.

1. Recursively calculate mid
2. Make it root node.
3. Nd keep doing this process for other two halves of array

T(n)=2T(n/2)+1
it will give us o(n) time complexity

space complexity-o(n) for recursive stack

public static TNode insert(TNode node, int value){
		if(node == null){
			node = new TNode(value);
		}else{
			if(value > node.value)
				node.right = insert(node.right,value);
			else
				node.left = insert(node.left,value);
		}
		return node;
	}

public static TNode createTree2(int array[], int start, int end, TNode root){

		if(start < 0 || end >= array.length || start > end){
			return root;
		}else{
			int middle = ((end - start)/2)+start;  // middle Index
			
			root =insert(root,array[middle]);
			createTree2(array,start,middle-1,root);
			createTree2(array,middle+1,end,root);
		}
		return root;
		
	}

Complexity:
Tree Insert O(n log n) + Iterate array O (n ) = O( 2n log n) ~ O (n log n )

Every time find the mid of the array/sub-array and make it as root.
e.g. array is 1,2,3,4,5,6,7,8,9
1. Find mid i.e. 5 which will be root.
2. Elements at the left hand side of 5 will be left sub tree and rest will be right sub tree.
3. Recursively call left and right sub array.

can we also use red-black tree instead and start inserting the first element from the beginning?

AVL tree implementation will suffice here.