A balanced tree with minimal rebalances.

MinimalBalancedTree.java

package trees;

import java.util.LinkedList;
import java.util.Queue;

/**
 * There are bugs around odd and even array length and last element being not added but this is the
 * general structure of the code.
 * 
 * @author amitsaurav
 *
 */
public class MinimalBalancedTree {
    /**
     * Inserts a sorted array into a tree and returns the head
     * 
     * @param array
     * @return Head of the BST
     */
    public Node insert(int[] array) {
        Queue<NodeRangeWrapper> q = new LinkedList<>();
        NodeRangeWrapper initialRange = new NodeRangeWrapper(0, array.length, array);
        q.add(initialRange);

        while (!q.isEmpty()) {
            NodeRangeWrapper currentRange = q.remove();
            if (currentRange.low < currentRange.mid - 1) {
                NodeRangeWrapper temp = new NodeRangeWrapper(currentRange.low, currentRange.mid, array);
                currentRange.node.left = temp.node;
                q.add(temp);
            }
            if (currentRange.mid < currentRange.high - 1) {
                NodeRangeWrapper temp = new NodeRangeWrapper(currentRange.mid, currentRange.high, array);
                currentRange.node.right = temp.node;
                q.add(temp);
            }
        }

        return initialRange.node;
    }

    /**
     * Prints the tree in level-order (for debugging purposes only)
     * 
     * @param head
     */
    public static void printTree(Node head) {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node n = queue.remove();
            System.out.println(n.value);
            if (n.left != null)
                queue.add(n.left);
            if (n.right != null)
                queue.add(n.right);
        }
    }

    public static void main(String[] args) {
        MinimalBalancedTree tree = new MinimalBalancedTree();
        Node root = tree.insert(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
        printTree(root);
    }

    private static class NodeRangeWrapper {
        final int low;
        final int high;
        final int mid;
        final Node node;

        public NodeRangeWrapper(int l, int h, int [] array) {
            low = l;
            high = h;
            mid = (l + h) / 2;
            node = new Node(array[mid]);
        }
    }

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

        public Node(int v) {
            value = v;
        }
    }
}