Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.

(a) True

(b) False

My question is taken from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms I

I got this question by my school principal while I was bunking the class.

1 Answers

Correct choice is (a) True

The best explanation: The worst case performance of binary tree sort is O(n log n) when it is implemented using a self balancing binary search tree. Self balancing binary search trees perform transformations to balance the tree, which caused balancing overhead. Due to this overhead, binary tree sort is slower than merger sort.