Why O(N Log N) to build Binary search tree?

Question

Getting ready for exam. This is not the homework question.

I figured that the worst case O(N^2) to build BST. (each insert req N-1 comparison, you sum all the comparisons 0 + 1 + ... + N-1 ~ N^2). This is the case for skewed BST.

The insertion for (balanced) BST is O(log N), so why the best case is O(N logN) to construct the tree ?

My guess best guess - since single insertion is log N, than summing all the insertions somehow gives us N log.

Thanks !

Answer 1

As you wrote :) Single insertion is O(log N).Because the weighted tree height of N element is log N you need up to log N comparsions to insert single element. You need to do N of these insertions. So N*logN.