Solution: Insert Every Element, Then Read In Order

Inserting the elements

Make a BinarySearchTree and add every element of the array to it:

BinarySearchTree<Integer> tree = new BinarySearchTree<>();
for (int value : arr) {
  tree.add(value);
}

That is $n$ calls to add. Each add follows one path down from the root, so it costs $O (h)$ , where $h$ is the tree’s height. When the tree stays balanced, $h$ is about $lo g n$ , so each add is $O (lo g n)$ and the $n$ inserts come to $O (n lo g n)$ .

The tree from the search tree chapter follows a no-duplicates rule, so a repeated value is dropped on its second add. So this treeSort assumes the values in the array are distinct. Sorting an array with repeats would need a tree that keeps duplicates, for example by storing a count at each node.

Reading them back in order

The tree from the search tree chapter iterates in order, so a for-each over it visits the values from smallest to largest. Write each one into the array, left to right:

int i = 0;
for (int value : tree) {
  arr[i] = value;
  i++;
}

The read-back visits each of the $n$ nodes once, so the read-back is $O (n)$ .

Putting it together

public static void treeSort(int[] arr) {
  BinarySearchTree<Integer> tree = new BinarySearchTree<>();
  for (int value : arr) {
    tree.add(value);
  }

  int i = 0;
  for (int value : tree) {
    arr[i] = value;
    i++;
  }
}

What it costs

The insert phase is $O (n lo g n)$ and the read-back is $O (n)$ , so treeSort is $O (n lo g n)$ when the tree stays balanced.

A plain binary search tree’s shape depends on the order the values arrive in, as the search tree chapter showed. On already-sorted input the tree does not stay balanced. Each new value is larger than everything already in the tree, so it goes to the right of every node, and the tree degenerates into a right-leaning spine, the linked-list shape from the search tree chapter:

╭───╮
│ 1 │
╰─┬─╯
  └───┐
    ╭─┴─╮
    │ 2 │
    ╰─┬─╯
      └───┐
        ╭─┴─╮
        │ 3 │
        ╰─┬─╯
          └───┐
            ╭─┴─╮
            │ 4 │
            ╰───╯

Now each insert follows a path through every node already in the spine, so the inserts sum to $0 + 1 + \dots + (n - 1)$ , and treeSort is $O (n^{2})$ on sorted input. This is the worst case that motivated the AVL tree. A balanced tree fixes it: the TreeMap chapter’s TreeMap keeps its keys in an AVL tree, so putting each value into a TreeMap as a key keeps the tree balanced and restores the $O (n lo g n)$ guarantee on every input.

Tree sort vs heapsort

Tree sort and heapsort are the same idea: insert the elements into a structure that keeps some order, then read them back in order. Tree sort builds a separate tree of node objects, each with a value and two child references, so it uses $O (n)$ auxiliary space and is not in place. It also needs AVL balancing to be $O (n lo g n)$ on every input. Heapsort does the same job inside the input array, needs no balancing, and is $O (n lo g n)$ on every input.