CareerCup

By using extra space, you can do an inorder traversal, and write the elements to the array.
After that, use binary search to find the middle element of the array and make it the root. Recursively invoke binary search on the left half and right half of the array to create left subtree and right subtree. This will give you a tree of min-height.

Without using extra space, you can first run a recursive procedure, which at each step, determines the heights of the left-subtree and right-subtree, and then does 'rotations' with either of the left/right children as pivot according to their heights.

This method would be terribly slow because at each recursive invocation to find the height of the tree, the whole sub-tree would be traversed.

It can be sped up by storing a height variable at each node of the tree and computing it's value only once, but then it amounts to using extra space.

Since the tree is sorted ..we can use a binary search style mid-point finding algorithm to get the root at each level...from skewed i assume that one sub-tree has more elements than the other sub-tree..meaning..in the array -- elements in one side of the mid-point is greater than the other...this could be handled by a simple if condition in the code..logic below---

space -- O(N) ==> one node element for each number .. time -- O(N.LogN) -==> binary search

// find midpoint
int mid-point(int left, int right){
	if(left==right) return left;
	return floor ((left+right) / 2)
}

// sample helper function to create a class node of type Node on a global array (in our case, input array) -- say 'a' 

Node node( int index){
	Node node = null;
	if (index >0) { return (new node (a[index]) )
	else return node
}


// form recursive BST from root at each level

void formBST (Node root, int left, int right) {
	if(left < 0 || right > a.size-1 || root == null) return;
	int x = mid-point(left, right);
 	root.left (node (mid-point(left, x-1) ) ) ; 
	root.right (node (mid-point(X+1, right) ) ) ;
	formBST (root.left, left, x-1) ; 
	formBST (root.right, x+1, right);
}

You do not need this mid-point function. Because once we have sorted array picking mid element suffices to construct balanced tree.

Suppose I have been given root of the skewed BinaryTree:

//Helper function to find size of tree
int size(BinaryTreeNode root){
	if(root == null) return 0;
	else{
		retrun(size(root.getLeft()) + 1+ size(root.getRight());
	}
}

// Inorder traversal

int[] inrderTraversal(BinaryTreeNode root){
	int[] inOrder = new int[size(root)];
	int index = 0;
	if(root != null){
		inrderTraversal(root.getLeft());
		inOrder[index++] = root.getData();
		inrderTraversal(root.getRight());
	}
}
// Minimum height tree creation
BinaryTreeNode buildBalancedTree(int[] inOrder, int start, int end){
	BinaryTreeNode treeNode;
	if(start>end) return null;
	treeNode = new BinaryTreeNode();
	if(start == end){
		treeNode.setData(inOrder[start]);
		treeNode.setLeft(null);
		treeNode.setRight(null);
	}else{
		int mid = start + (end-start)/2;
                treeNode.setData(inOrder[mid]);
		treeNode.setLeft(buildBalancedTree(inOrder, start, mid-1));
		treeNode.setRight(buildBalancedTree(inOrder, mid+1,end));
	}
	return treeNode;
}

// testing the APIs, rrot is the root of skewed binary tree in question
int n = size(root);
int startIndex= 0;
int[] inOrder = inrderTraversal(root);
BinaryTreeNode balancedTree = buildBalancedTree(inOrder, 0, n-1);