Solving The Min Height Binary Search Tree in Python

The Prompt

Create a function that takes in a non-empty sorted array of integers, creates a Binary Search Tree (BST) from the integers, and returns the root of the BST.

The function should minimize the height of the BST.

The Code

Given a BST class.

We need to create the function, and the logic to get fulfill the requirements of the problem.

In order to solve the problem, one way would be to create a helper function. The helper will take in the following parameters:

• array
• BST
• starting index
• ending index

First off, we can initiate with the logic if the ending index is smaller than the starting index, return None.

Also, at this point, we can create two variables, one to represent the midpoint , and another for the value we need to add to the BST.

Now, using an if/else loop, if the BST is None, create the BST with the (value) variable.

Else, insert the value into the (bst).

Finally, using recursion, we can implement the helper function twice. The code should look like the following:

And there you have, the code and solution is complete. The final code is referenced below:

Complexity Analysis

The time complexity of this solution is O(n log(n)) time, where (n) is the length of the input array.

The space complexity of this solution is O(n) space, where (n) is the length of the final BST.