Solution: Choosing the Middle as the Root

Start with an easier problem. Suppose the seven values are already out of the tree, in a sorted list: [20, 30, 40, 50, 60, 70, 80]. How do we build a balanced tree from them?

The chain happened because the first value added became the root, and it was the smallest value, so every other value went to its right. The fix is to choose a better root.

For a balanced tree, the root should split the values evenly: about half smaller, half larger. With the list already sorted, the value that does that is the one in the middle. Make it the root. The values to its left form the left subtree, and the values to its right form the right subtree.

Each half is itself a sorted range, so build it the same way: pick its middle as the subtree’s root, and recurse. This is divide and conquer over index ranges.

private static <T> Node<T> buildBalanced(List<T> sorted) {
  return build(sorted, 0, sorted.size() - 1);
}

private static <T> Node<T> build(List<T> sorted, int lo, int hi) {
  if (lo > hi) {
    return null;
  }

  int mid = (lo + hi) / 2;
  Node<T> node = new Node<>(sorted.get(mid));
  node.left = build(sorted, lo, mid - 1);
  node.right = build(sorted, mid + 1, hi);
  return node;
}

The range lo..hi is the slice of the list a call is responsible for. When lo > hi, the slice is empty, so the call returns null. That is what gives the leaves their null children. Otherwise the middle index becomes this subtree’s root, and the two halves on either side become its children.

Trace it on [20, 30, 40, 50, 60, 70, 80], whose indices run 0 through 6.

The first call gets the whole list. Its middle is index (0 + 6) / 2 = 3, the value 50:

┌────┬────┬────┬────┬────┬────┬────┐
│ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ 80 │
└────┴────┴────┴────┴────┴────┴────┘
                  ↑
                 mid

╭────╮
│ 50 │
╰────╯

Now build recurses on the left half (indices 0..2) for the left child and on the right half (indices 4..6) for the right child. The middle of 0..2 is index 1, the value 30; the middle of 4..6 is index 5, the value 70:

┌────┬────┬────┬────┬────┬────┬────┐
│ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ 80 │
└────┴────┴────┴────┴────┴────┴────┘
        ↑                   ↑
       mid                 mid

     ╭────╮
     │ 50 │
     ╰──┬─╯
   ┌────┴────┐
╭──┴─╮    ╭──┴─╮
│ 30 │    │ 70 │
╰────╯    ╰────╯

Each remaining range now holds a single index. build(sorted, 0, 0) returns a leaf 20, build(sorted, 2, 2) a leaf 40, and likewise 60 and 80 on the right. Their own recursive calls get empty ranges (lo > hi) and return null, so these four nodes are leaves:

┌────┬────┬────┬────┬────┬────┬────┐
│ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ 80 │
└────┴────┴────┴────┴────┴────┴────┘
   ↑         ↑         ↑         ↑
  mid       mid       mid       mid

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │ 60 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

This is exactly the balanced tree from the problem page. The seven values that formed a chain of height $6$ when added one at a time form a tree of height $2$ here, with no rotations.

Why no rotations

Notice that the code never calls compareTo. The list is already sorted, so the order is fixed. Everything left of mid is smaller and everything right of mid is larger, which is the BST ordering property. Choosing the middle as the root makes the split even, which keeps the tree balanced. Both properties hold by construction.

One-at-a-time insertion is different because it cannot choose the root. It must take the values in the order they are inserted. A bad insertion order, like sorted input, produces a lopsided tree, and a rotation fixes it afterward. Here there is no insertion order. We have every value at once and place each one in its final position, so there is nothing to fix.

Cost

build is called once for each index, plus the empty-range calls at the bottom, so the work is $O (n)$ . The recursion goes only as deep as the tree is tall, which is $O (lo g n)$ , so the call stack stays shallow. The tree it produces has height $⌊ lo g_{2} n ⌋$ , the smallest height $n$ nodes can have, because every split is as even as it can be.