Question

What is the worst case time complexity of the binary tree sort?

(a) O(n)

(b) O(nlogn)

(c) O(n^2)

(d) O(logn)

I got this question during a job interview.

Question is taken from Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (c) O(n^2)

Explanation: For the binary tree sort the worst case when the BST constructed is unbalanced. BST gets unbalanced when the elements are already sorted. So, in the worst case, O(n^2) time is required to built the BST and O(n) time to traverse the tree. Therefore, the worst case time complexity is O(n^2) + O(n) = O(n^2).