Question

The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree.

(a) True

(b) False

The question was posed to me during an interview.

This interesting question is from Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

The correct choice is (b) False

The explanation is: The time complexity of tree sort is affected when implemented with an unbalanced tree or a balanced tree. In case of a balanced tree it is O(n log n) and in case of unbalanced tree it is O(n^2).