Problem
You are given a set of n real numbers which you are asked to insert incrementally in an initially empty binary search tree. Note that the time to insert an element in a binary search tree of size r is O(log s). What is the total running time of inserting all the n elements in the tree. Justify your answer. Assume that you have formed the binary search tree on n elements, show how you can report the elements in a sorted order in O(n) time.