BuildTree.java

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

class Node {
	Node left;
	Node right;
	int value;

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

public Node buildTree(int[] values) {

  int rootIndex = (int) Math.floor(values.length / 2);
  Node root = new Node(values[rootIndex]);

  addChildren(root, true, values, 0, rootIndex - 1);
  addChildren(root, false, values, rootIndex + 1, values.length - 1);

  return root;
}

public void addChildren(Node parent, boolean rightChildren, int[] values, int min, int max) {

  if (min > max) {
    return;
  }

  if (parent == null) {
    return;
  }

  int rootIndex = (int)Math.floor((min + max) / 2);
  Node children = new Node(values[rootIndex]);

  addChildren(children, true, values, min, rootIndex - 1);
  addChildren(children, false, values, rootIndex + 1, max);

  if (rightChildren) {
    parent.right = children;
  } else {
    parent.left = children;
  }
}