Sorted Array to BST

You are given an array which is sorted in increasing order, you need to convert that array into a Binary Search Tree. Note that the given sorted array is the inorder traversal of the BST.

Consider the array given below.

Arr = {1, 3, 4, 6, 7, 8, 10, 13, 14}.
The binary search tree corresponding to the given array is

Algorithm

The algorithm is similar to binary search algorithm. If the starting index is less than the ending index, we do the following.
Calculate the middle index from the starting and ending indices. Create a node with the value in the middle index of the array.
Make a recursive call to the function with the starting index as the previous starting index and the ending index as (middle index – 1). Thus, the array for the new recursive call becomes Arr [start ….. (mid – 1)]. Set the node returned from this recursive call to the left child of the current node.
Make another recursive call to the right part of the array i.e Arr [(mid+1) …. end] and set the node returned from it to the right child of the current node. Finally return the current node.

For a better understanding, check out the code below.

#include <bits/stdc++.h>
using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}



void levelOrderTraversal(Node* root){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

Node* sortedArrayToBST(vector<int> arr, int start, int end)  
{  
    /* Base Case */
    if (start > end)  
    return nullptr;  
  
    /* Get the middle element and make it root */
    int mid = (start + end)/2;  
    Node *root = createNode(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;  
}  

int main()
{
	vector<int> arr = {1, 3, 4, 6, 7, 8, 10, 13, 14};
    Node* root = sortedArrayToBST(arr, 0, 8);
    levelOrderTraversal(root);
    cout<<endl;
    return 0;
}

Also check another popular interview problem Count of leaf nodes.

One comment

Leave a Reply

Your email address will not be published.