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?

(Note that calling TREE-INSERT on a tree of height \(x\) takes \(\Theta(x)\) time and an inorder tree walk on a binary search tree with \(y\) nodes takes \(\Theta(y)\) time.)

In the worst-case, our set of \(n\) numbers is already sorted in which case the \(n\) successive calls to TREE-INSERT produce a binary search tree of height \(n\). The runtime in this secnario is \(\Theta(n^2 + n) = \Theta(n^2)\).

In the best-case, successive calls to TREE-INSERT on our set of \(n\) numbers produces a balanced tree such that the height does not exceed \(\lg n\). In this case, the runtime is \(\Theta(n \lg n + n) = \Theta(n \lg n)\).