The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.

Category: QuestionsThe binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
Editor">Editor Staff asked 1 month ago

The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
 
(a) O(n log n)
 
(b) O(n)
 
(c) O(n^2)
 
(d) O(log n)
 
I’d like to ask this question from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms I
 
The question was posed to me at a job interview.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct choice is (a) O(n log n)
 
Best explanation: The worst case running time of the binary tree sort is O(n^2). But, the worst case running time can be improved to the O(n log n) using a self – balancing binary search tree.