Minimal Tree

Given an array with unique integer elements, sorted in increasing order, write an algorithm to create a binary search tree with minimal height.

Solution

The root of the binary search tree will be the middle element of the sorted array. Similarly, the children of the root will be the middle of the subarrays defined by the middle element. One solution would involve using the BinarySearchTree class, and inserting elements one by one into the tree. However, this is not optimal, as the insert method takes time \(O(log \ n)\), so in total this algorithm would take time \(O (n \ log \ n)\).

A different algorithm involves constructing the binary search tree from scratch, using a recursive algorithm. We can assign children to each node by selecting the middle of the right and left subarrays. If we call this function recursively, we will construct the binary search tree.

First, we will need our Node class.

class Node:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None

Now, we can construct the algorithm.

def create_binary_tree(array, start, end):
  if (end < start) or (start > len(array)):
    return None

  mid = (start + end) / 2

  node = Node(array[mid])
  node.left = create_binary_tree(array, start, mid - 1)
  node.right = create_binary_tree(array, mid + 1, end)

  return node