MINIMUM HEIGHT BST

 Given a non-empty sorted array of distinct integers, construct a minimum height bst and return       root .

Approach : Since the array is element at the middle of array is going to be the root.

So we will try break the array in 3 parts( left array, middle element, right array).

Middle element will be the root of the array, then we will find the middle of left array it will be the root of left sub tree and similarly the middle of right array will be the root of right sub tree.

         We defined tree as None since there is no node in the tree.

Now we will be inserting nodes in the tree using minHeightBstHelper function.  

 

 

         BST is a class which inserts the node at its right place following the bst properties.

Time - O(n log n) 

Space - O(n) 

Solution - min height bst solution

Can you reduce its time complexity of O(n), do post the solution in comment.

Please leave comment for any suggestions or topic you would like to read.