Question:- Given an integer array
nums where the elements are sorted in ascending order, convert it to a binary search tree with minimum height.
Input: [1, 2, 3]
Input: [1, 2, 3, 4]
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 firstname.lastname@example.org.
For more updates, let’s connect on LinkedIn .