Convert Sorted Array to Binary Search Tree

Divya Biyani
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
/
1
OR 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.

For more updates, let’s connect on LinkedIn .

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/.

Divya Biyani

Written by

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/.