# Convert Sorted Array to Binary Search Tree

Mar 3 · 2 min read

Hey Guys, Welcome Back! This blog is in continuation with our series of solving a question a day.

Question:- Given an integer array `nums` where the elements are sorted in ascending order, convert it to a binary search tree with minimum height.

Example:-

`Input:  [1, 2, 3]Output:     2   /  \  1    3 Input: [1, 2, 3, 4]Output:       3    /  \   2    4  /1OR      2    /  \   1    3         \          4`

Solution:-

After reading the question and the requirement to create a binary search tree with minimum search height, it became clear that we need to create a balanced binary search tree.

A balanced binary tree is a binary tree in which the height of the two subtrees of every node never differs by more than one.

When it comes to the binary tree, I immediately start looking for a recursive solution.

In order to make a binary search tree, we need to always have an equal no. of elements( or the difference should be ≤1 between no of left node children’s and right node children’s).

Hence, given an array, we should always choose the middle element as the root. (Any middle element in case of even number length array).

So, based on this we can create a recursive pseudo code,

`1.) Choose the middle element of array and make it root.2.) Recursively do the same for the left and right children -2.a) root.left = createBalancedBST(arr, start, mid-1)     For the left children, since in a BST all left children should be <= the root, hence we will create a Balanced BST from start of the subarray to the mid-1.2.b) root.right = createBalancedBST(arr, mid+1, end)     For the right children, since in a BST all left children should be >= the root, hence we will create a Balanced BST from mid+1 of the subarray to the end.`

Below is the code implementation in java for the problem based on my approach -

Time Complexity:- O(n)
Since each element gets traversed once, hence the overall time complexity of the problem is linear.

Book to read for data structures and algorithms -

That’s all from my side, thank you so much for reading the blog. I will be continuing this series and will keep on discussing everyday problems. For any further discussions, please feel free to reach out to me at divyabiyani26@gmail.com.

## Nerd For Tech

From Confusion to Clarification

## Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/. Don’t forget to check out Ask-NFT, a mentorship ecosystem we’ve started

Written by

## Divya Biyani

Software Developer by profession, with a passion of sharing knowledge.

## Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/. Don’t forget to check out Ask-NFT, a mentorship ecosystem we’ve started

## How to Deploy Your Qt Cross-Platform Applications to Windows Operating System By Adding Manually…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app