Exercise 12.1.5
Argue that since sorting elements takes time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of elements takes time in the worst case.
Let's make a reductio ad absurdum argument.
Let's assume that there exists algorithm for constructing a binary search tree of elements. We can then use it to create a tree of elements and then use an inorder walk to gather the elements in an array in time. This way we will produce an sorted array in worst-case time, which contradicts with the lower bound on comparison sort.