Home » Interview coding problems/challenges

Convert Sorted Array to Binary Search Tree

In this article, we are going to see how to convert a sorted array into a binary search tree? This problem can be featured in coding interview rounds. Submitted by Radib Kar, on January 14, 2019

Problem statement

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Let the sorted array to be:
[-1, 3, 6, 8]
The corresponding balanced BST is:
               3
             /   \
           -1     6
                    \
                      8

Solution:

The algorithm is simply finding the median in the sorted array and assigning it as a root. Then process the subtrees recursively.

Let the function to build the balanced BST from the sorted array is:

buildBST() which has parameters: sorted array, lower index, higher index

has return type: TreeNode* // returns the root actually

Function buildBST(sorted array, lower index , higher index)
    1.  Base case:
        IF lower index>higher index
            Return NULL
    2.  Declare middle index as (lower index + higher index)/2
    3.  root=createnode(array[middle index]);
    4.  Create the left subtree recursively
        Root->left=buildBST(sorted array, lower index, middle index-1)
    5.  Create the right subtree recursively
        Root->left=buildBST(sorted array, middle index-1,higher index)
    6.  Return root
END FUNCTION

In the main function we call,

    Root=buildBST (sorted array, 0, size of array-1)

C++ implementation

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

// TreeNode node type
class TreeNode{
	public:             
		int val;           //value
		TreeNode *left;    //pointer to left child
		TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(int data)  
{ 
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); 
	node->val = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
}

TreeNode* buildBST(vector<int> nums,int low,int high){
	if(low>high)
		return NULL;
	
	int mid=(low+high)/2;
	TreeNode* root=newnode(nums[mid]); //creates new nodes
	root->left=buildBST(nums,low,mid-1);
	root->right=buildBST(nums,mid+1,high);

	return root;
}


TreeNode* sortedArrayToBST(vector<int>& nums) {
	TreeNode* root=buildBST(nums,0,nums.size()-1);
	return root;
}

void levelOrder(TreeNode* root) {
	cout<<"root: \n";
	queue<TreeNode*> q;

	if(root==NULL){
		cout<<"empty tree\n";
	}
	
	int count=1;		
	TreeNode* temp;
	q.push(root);
	q.push(NULL);

	while(!q.empty()){
		temp=q.front();
		q.pop();
		if(temp==NULL){
			if(!q.empty()){
				cout<<"\nend of level: "<<count++<<endl;
				q.push(NULL);
			}
		}
		else{
			cout<<temp->val<<" ";
			if(temp->left)
				q.push(temp->left);
			if(temp->right)
				q.push(temp->right);
		}
	}
	cout<<"\nend of level: "<<count<<endl;
}

int main(){
	int n,no;
	
	cout<<"enter no of elements\n";
	cin>>n;
	vector<int> v;
	
	cout<<"enter the sorted array\n";
	while(n--){
		cin>>no;
		v.push_back(no);
	}
	
	TreeNode* root=sortedArrayToBST(v);
	cout<<"displaying level order traversal\n";
	levelOrder(root);

	return 0;
}

Output

enter no of elements
4
enter the sorted array
-1 3 6 8
displaying level order traversal
root:
3
end of level: 1
-1 6
end of level: 2
8
end of level: 3

Example with explanation

For simplicity all nodes are represented by its value
Let the sorted array to be:
A=-1, 3, 6, 8

So in the main function it calls:
Root=buildBST( A, 0, 3)
---------------------------------------------------

buildBST( A, 0, 3)
base case isn’t met
mid= 1
root= A[1]=3 
3->left=buildBST( A, 0, 0)
3->right= buildBST( A, 2, 3)
Return 3 (node)
---------------------------------------------------

buildBST( A, 0, 0)
base case isn’t met
mid= 0
root= A[0]=-1
-1->left=buildBST(A, 0, -1)
(-1)->right= buildBST(A, 1, 0)
Returns -1(node)
---------------------------------------------------

buildBST( A, 2, 3)
base case isn’t met
mid= 2
root= A[2]=6
6->left=buildBST(A, 2, 1)
(6)->right= buildBST(A, 3, 3)
Returns 6(node)
---------------------------------------------------

buildBST( A, 0, -1)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 1, 0)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 2, 1)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 3, 3)
base case isn’t met
mid= 3
root= A[3]=8
8->left=buildBST(A, 3, 2)
(8)->right= buildBST(A, 4, 3)
Returns 8(node)
---------------------------------------------------

buildBST( A, 3, 2)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 4, 3)
base case is met
Returns null


So,
8->left=NULL
8->right=NULL
6->left=NULL
6->right=8
-1->left=NULL
-1->right=NULL
3->left=-1
3->right=6

So the tree becomes:
               3
            /    \
         -1       6
                   \
                    8