Solution: Flatten, Then Rebuild

The previous solution builds a balanced tree from a sorted list. What is left is getting that sorted list out of the skewed tree, so the method has two steps.

The first step turns the tree into a sorted list. An in-order traversal of a binary search tree visits its values from smallest to largest, which we saw in the search tree chapter. So an in-order traversal of the skewed tree gives us every value, already in order.

The second step turns that sorted list back into a balanced tree. That is the previous solution: from a sorted sequence, pick the middle as the root, and recurse on each half.

Put the two together:

public static <T> Node<T> balance(Node<T> root) {
  List<T> values = new ArrayList<>();
  inOrder(root, values);
  return buildBalanced(values);
}

private static <T> void inOrder(Node<T> node, List<T> out) {
  if (node == null) {
    return;
  }
  inOrder(node.left, out);
  out.add(node.value);
  inOrder(node.right, out);
}

buildBalanced is the method from the previous solution. Notice the signature does not need Comparable. The in-order traversal reads the order that is already in the tree, and buildBalanced compares nothing.

Tracing it

Take the skewed tree of 20 through 80 from the problem.

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

Step one runs inOrder on it. The traversal goes as deep left as it can first, but every node’s left child is null, so it visits each node and immediately moves to the right child. The values come out in order from the root down:

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

The shape of the input does not matter. Any binary search tree holding these values would flatten to this same list.

Step two passes that list to buildBalanced. This is the trace from the previous solution: the middle value 50 becomes the root, the left half 20 30 40 builds the left subtree, the right half 60 70 80 builds the right subtree, and each half splits at its own middle. The result:

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

The tree now has height $2$ .

Cost

The in-order traversal visits each node once, which is $O (n)$ , and fills a list of size $n$ . The buildBalanced step is $O (n)$ as well, as we saw in the previous solution. So the whole method is $O (n)$ time and $O (n)$ extra space for the list. That is faster than the $O (n lo g n)$ of re-inserting every value.