Algorithm Problem: Linear Time Sorting

Please include all the steps and details for learning purposes.

1. Given the keys 16, 11, 5, 37, 15, 33, 27, 4, 13, create a binary search tree by using Tree-Insert repeatedly to insert the number one by one in the given order (show the successive steps);

We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?

Is the operation of deletion commutative in the sense that deleting x and then y from a binary search tree leaves the same tree as deleting y and then x? Argue why it is or give a counterexample using the BST from (1).