Alg.22 Min Height BST

From algoexpert.io

Given a sorted array (each element is distinct), write a function to construct a BST with min height.

Here is the structure of BST, and we provide a insert function which can insert an element to a given BST in O(logn).

static class BST {
  public int value;
  public BST left;
  public BST right;

  public BST(int value) {
    this.value = value;
    left = null;
    right = null;
  }

  public void insert(int value) {
    if (value < this.value) {
      if (left == null) {
        left = new BST(value);
      } else {
        left.insert(value);
      }
    } else {
      if (right == null) {
        right = new BST(value);
      } else {
        right.insert(value);
      }
    }
  }
}

The basic idea is: try to allocate the elements evenly, since the array is sorted, we try to make the left and right subtree have the same amount of elements. So, we can let the middle point be the root node, and repeat this operation on the left and right subtree recursively. In the solution, we call the minHeightBstHelper function recursively.

public static BST minHeightBst(List<Integer> array) {
  return minHeightBstHelper(array, 0, array.size() - 1);
}

Here is one solution with the given insert function.

public static BST minHeightBstHelper(List<Integer> array, BST bst, int start, int end) {
    if (start > end) return null;
    
    int midIdx = start + (end - start) / 2;
    int mid = array.get(midIdx);
    
    if (bst == null) bst = new BST(mid);
    else bst.insert(mid);
    minHeightBstHelper(array, bst, start, midIdx - 1);
    minHeightBstHelper(array, bst, midIdx + 1, end);
  return bst;
}

Time complexity: O(nlogn); Space complexity: O(n).

Now, we can implement our own insert operation, in this case, this solution will be completed in O(n).

public static BST minHeightBstHelper(List<Integer> array, BST bst, int start, int end) {
    if (start > end) return null;
    int midIdx = start + (end - start) / 2;
    int mid = array.get(midIdx);
    BST newNode = new BST(mid);
    if (bst == null) {
        bst = newNode;
    } else if (bst.value > mid) {
        bst.left = newNode;
        bst = newNode;
    } else {
        bst.right = newNode;
        bst = newNode;
    }
    minHeightBstHelper(array, bst, start, midIdx - 1);
    minHeightBstHelper(array, bst, midIdx + 1, end);
    return bst;
}

Time complexity: O(n); Space complexity: O(n).

The third way is a simplified version of the second way.

public static BST minHeightBstHelper(List<Integer> array, int start, int end) {
    if (start > end) return null;
    int midIdx = start + (end - start) / 2;
    int mid = array.get(midIdx);
    BST bst = new BST(mid);
    bst.left = minHeightBstHelper(array, start, midIdx - 1);
    bst.right = minHeightBstHelper(array, midIdx + 1, end);
    return bst;
}

Time complexity: O(n); Space complexity: O(n).

Donate