Convert sorted array to balanced binary search tree

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)

2 Thoughts on “Convert sorted array to balanced binary search tree

  1. Pingback: Sorted Linked List to Balanced Binary Search Tree

  2. Santosh Kumar on September 6, 2015 at 2:06 am said:

    http://www.youtube.com/watch?v=VCTP81Ij-EM Here is video for converting sorted array to balanced BST.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation