javed.937
BAN USERThis 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;
}
Storing inn BST means you are sorting it which is prohibited. A min_heap is a correct solution
- javed.937 August 24, 2015