Problem : Given a sorted array . Write a program to create balanced BST from the sorted array.
We know that the in-order traversal of binary search tree gives the elements in sorted order. This tells us that the middle element of array will be the root. We can create left and right subtree by recursively calling same function for left and right subarray.
struct node { int value; struct node* left; struct node* right; }; struct node* newNode(int value) { struct node* newnode = (struct node*)malloc(sizeof(struct node)); newnode->value = value; newnode->left = NULL; newnode->right = NULL; return newnode; } struct node *arrayToBST(int arr[],int start,int end) { if (start > end) return NULL; int mid = start + (end - start) / 2; struct node *root = newNode(arr[mid]); root->left = arrayToBST(arr, start, mid-1); root->right = arrayToBST(arr, mid+1, end); return root; }
Time Complexity : O(n)
Pingback: Sorted Linked List to Balanced Binary Search Tree
http://www.youtube.com/watch?v=VCTP81Ij-EM Here is video for converting sorted array to balanced BST.