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.




Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

7 Tools To Make Kubernetes Management Easy

End of support for CloudApp

UML Sequence Diagram Through “The Little Prince” Narrator’s Interactions With the Outside World

Migrating Data and Userbase from Salesforce into JIRA

Code Retreat is RETRO

Cookies and Sessions: A Gentle Introduction With PHP

Join the #100daysofcode challenge now.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Karan S. Chauhan

Karan S. Chauhan

More from Medium

Fundamental concepts of every programming language

Top 8 Features of Python Language That You Must Know

Top 8 Python Features

Python simple debugging beyond print() with Icecream

Run Python in browser using Skulpt: Part 1: The basic stuff