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