CareerCup

Not possible. Have to visit each element.

an array is already a balanced btree. r u talking about bst?

Nope not possible in logn....actually i think it cannot be done in linear time also...it require o(logn) to lookup in a btree.. also just traversing the leaves of btree gives the array in sorted order. Minimum complexity for a comparision based sort is o(nlogn)

This works only for sorted array!

...you want to visit N elements in log(N) time?

Please correct me if I am wrong. This is to create a BST.
1) Here we calculate the pivot using the partition function:
This will split the array into 2 sub-arrays

public static int partition(int[] a, int l, int r) 
    {
        
        int m=(l+r)/2;
        swap(a,l,m);
        int pivot=a[l];
        int low=l+1;
        int high=r;
        while(low<=high)
        {
            while(a[high]>pivot)
                high--;
            while(low<=high && a[low]<pivot)
                low++;
            if(low<=high)
            {
                swap(a,low,high);
                low++;high--;
            }
        }swap(a,l,high);
        System.out.println("Here the partition is: "+a[high]);
        return high;
    }

This function should return the root in the 1st case and the node in the later iterations.
2) Now the quicksort on the subarrays leads to further partitions which will be nodes.
The lower subarray will be the left subtree and the higher would be the right subtree.

quickSort(a,p,q);//left subtree
quickSort(a,q+1,r);//right rightsubtree

add all aliment into RBtree which will converter unsorted array into balanced BST. Complexity: nlogn


void RB_BST::insert(int d){

if(!root) {
node *tmp = new node(d,NULL,NULL,false);
root = tmp;
} else {
root = insertInt(root,d);
}
}

RB_BST::node* RB_BST::insertInt(node*p, int d) {
if(d < p->data) {
if(p->left) {
p->left = insertInt(p->left,d);
} else {
p->left = new node(d,NULL,NULL,true);
}
} else if(d > p->data) {
if(p->right) {
p->right = insertInt(p->right,d);
} else {
p->right = new node(d,NULL,NULL,true);
}
} else {
cout << "duplicate data"<<endl;
}
if(p->right && p->right->isRed == true) {
p = leftRotate(p);
}
if(p->left && p->left->isRed == true && p->left->left && p->left->left->isRed) {
p = rightRotate(p);
}
if(p->left && p->left->isRed == true && p->right && p->right->isRed == true) {
flipLink(p);
}
return p;

}

This can be done in O(n) time and O(n) space. Basically this is a classic example of level order traversal.
Alogithm:
1. Create the root element and insert into a queue
2. Loop throw the queue
3. Remove first element from the queue and create its both children and insert both children into the queue.
4. Repeat the step 3 until you have processed the whole array. This will create a Balanced binary tree.
=========================

There is one more algorithm to do it in O(n) time and O(1) space.
See this link.
http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
Here if array is not sorted then it will create a non BST

/* A function that constructs Balanced Binary Search Tree from a sorted array */
struct TNode* sortedArrayToBST(int arr[], int start, int end)
{
    /* Base Case */
    if (start > end)
      return NULL;
 
    /* Get the middle element and make it root */
    int mid = (start + end)/2;
    struct TNode *root = newNode(arr[mid]);
 
    /* Recursively construct the left subtree and make it
       left child of root */
    root->left =  sortedArrayToBST(arr, start, mid-1);
 
    /* Recursively construct the right subtree and make it
       right child of root */
    root->right = sortedArrayToBST(arr, mid+1, end);
 
    return root;
}

Use a recursive approach to achieve a linear logarithmic complexity. Let's see this in action:

/* Create a wrapper function*/
	TreeNode createBalancedTree(int[] array) {
		return createBalancedTree(array, 0, array.length - 1); 
	}

	/* Recursive function*/
	TreeNode createBalancedTree(int[] array, int min, int max) {
		if (max < min) return null;
		int mid = (min + max) / 2;
		TreeNode node = TreeNode(array[mid]);
		node.setLeftChild(createBalancedTree(array, min, mid - 1));
		node.setRightChild(createBalancedTree(array, mid + 1, max));
		return node;
	}

PS: This also create a balanced binary search tree, so we kill 2 birds with a stone.

To use this function simply create an array as below:

int[] array = {1, 4, 2, 5, 3};
	TreeNode node = createBalancedTree(array);