Create Minimal BST

Lessons Learned: Binary Search Tree, recursion

Question 6: Given a sorted array of unique numbers, write an algorithm to create a binary search tree with minimal height.

First off, let’s make sure we understand what a binary search tree is. A binary search tree is a binary tree such that the left subtree of a node always contains lesser values, and the right subtree of a node always contains greater values.

When we think about a minimal height tree, we can think about what this implies. We want the number of nodes in the left subtree to equal the number of nodes in the right subtree as much as possible. This means our root node must be the middle element in the array since the array is sorted. Therefore, the left half of the array will be our left subtree, and the right half of the array will be our right subtree. This can now be turned into a recursive process, where halves of the array are converted into subtrees until there are no values left.

We can define our recursive algorithm like so:

  1. Insert into the tree the middle element of the array.

  2. Insert (into left subtree) left subarray elements.

  3. Insert (into right subtree) right subarray elements.

  4. Recurse (repeat)

The code below is an implementation of the above algorithm:

We’re done!