Consider the Tree Sort algorithm in which sorting is achieved by placing all elements to be sorted into a binary search tree and then taking the in-order traversal of the tree. Another sorting algorithm, AVL Tree Sort, places all elements into an AVL tree and then takes the in-order traversal of the tree. Which of the following statements is/are true about Tree Sort and AVL Tree Sort? A. Tree Sort and AVL Tree Sort both perform well on input that is already in nearly sorted order.
B. The best case time complexity of Tree Sort is O(n log n).
C. The worst case time complexity of AVL Tree Sort is ?(n2).
D. The best case space complexity of Tree Sort is 0(n).
E. The best case space complexity of AVL Tree Sort is ?(log n).