Minimal Tree

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

The goal

If we use a standard Binary Tree traversal, we should be able to do this with On time complexity according to the Master Theorem application to common algorithms.

Naive Solution

My initial solution looked like this:

function minimalTree(arr) {
  if (arr.length === 0) {
    return null;
  }
  if (arr.length === 1) {
    return new BinaryTree(arr[0], null, null);
  }
  const centreIndex = Math.floor(arr.length / 2);
  const left = minimalTree(arr.slice(0, centreIndex));
  const right = minimalTree(arr.slice(centreIndex + 1));
  return new BinaryTree(arr[centreIndex], left, right);
}

But there's a problem here. Array.prototype.slice is not a constant time operation. It is On, where n is the start and end indices. In order for our Binary Tree Traversal to fit with the Master Theorem application, it needs to be doing constant time operations in each recursive call.

But since ours is doing a linear operation each time, the time complexity looks more like Merge Sort. To unpack with our example, the calls to minimalTree at each level of recursion look like this.

arr.length is our n: 8 in this example:

[-23, 0, 35, 44, 100, 101, 165, 200] // 8 operations
[-23, 0, 35] [100, 101, 165, 200] // 7 operations
[-23] [35] [100] [165, 200] // 5 operations
[200] // 1 operation

Instead of our target n, we're getting something like n/2 * log N, which is O(n log n).

Better Solution

The only reason we are getting O n log n results is because of arr.slice and its pesky On time complexity. How can we implement a similar algorithm without arr.slice?

Instead of manipulating the array, we can pass the indices of the array to process without sliceing it. We create an inner function to do the heavy lifting, and return the result of calling that function with the outside bounds of the array.

Solution

// You can check out the Binary Tree Playground to see how this works.
import { BinaryTree } from "data-structures";

function minimalTree(arr) {

  function inner(i, j) {
    if (i === j) {
      return null;
    }
    if ((j - i) === 1) {
      return new BinaryTree(arr[i], null, null);
    }
    const centreIndex = i + Math.floor((j - i) / 2);
    const left = inner(i, centreIndex);
    const right = inner(centreIndex + 1, j);
    return new BinaryTree(arr[centreIndex], left, right);
  }

  return inner(0, arr.length);

}

export default minimalTree;

Big O Analysis

Time Complexity: O(n)

Explanation: Since the array is already sorted, we should be able to do this in linear time.