Problem: Sort with a Search Tree

In this chapter we sorted by adding elements to a heap and taking them out in order. A binary search tree can sort the same way, and you already built one in the search tree chapter.

Recall from the search tree chapter that an in-order traversal of a binary search tree visits its values from smallest to largest.

Exercise

Using the BinarySearchTree from the search tree chapter, write treeSort that sorts an array of distinct int values into ascending order:

public static void treeSort(int[] arr) {
  // ...
}

Build it in two pieces:

insert: add every element of the array to a BinarySearchTree, reusing the tree’s add.
read back: iterate the tree in order, writing the values into the array in the order the iteration visits them.

For example, treeSort on [4, 2, 6, 1, 3, 5]

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 4 │ 2 │ 6 │ 1 │ 3 │ 5 │
└───┴───┴───┴───┴───┴───┘

adds those values to a search tree, building this shape:

               ╭───╮
               │ 4 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 2 │               │ 6 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 1 │     │ 3 │      │ 5 │
╰───╯     ╰───╯      ╰───╯

Reading the tree back in order writes the values into the array sorted:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │
└───┴───┴───┴───┴───┴───┘

Before opening the solution, answer two questions:

What is the total cost of treeSort?
What happens to that cost if the array is already sorted?