Problem: Balancing a Binary Search Tree

A binary search tree can satisfy the ordering property and still have a bad shape. The ordering property says nothing about height, so the same values can end up in a tall, skewed tree where lookups are slow.

Use the binary tree node from the tree chapter:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;

  public Node(T value) {
    this.value = value;
  }
}

Write this method:

public static <T> Node<T> balance(Node<T> root) {

}

An empty tree gives an empty tree, so return null.

Height-balanced means the same property the AVL tree maintains: at every node, the heights of the two subtrees differ by at most $1$ .

Here is the kind of input we want to fix. In the search tree chapter we saw that adding sorted values one at a time produces a single chain of nodes. Suppose someone built that tree by inserting the values 20 through 80 in order, so each value became the right child of the one before it:

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

This is a valid binary search tree. Every left child is smaller than its parent, and every right child is larger. But its height is $6$ , so a lookup can take seven steps when it should take three.

We want to keep the same seven values and return this tree instead:

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

This tree has height $2$ , and every subtree is height-balanced.

The obvious approach is to insert every value into a fresh AVL tree. That works, and the result is balanced, because the AVL tree rotates back to balance after each insertion. But each insertion costs $O (lo g n)$ , so the $n$ insertions cost $O (n lo g n)$ . Aim for $O (n)$ .

Try it before reading the solution.