Time and Space complexity of a Balanced Binary Search Tree

Question

What is computational complexity(time and space complexity) of building a Balanced Binary Search Tree?

Answer 1

The time complexity to build a BST with n nodes is O(n*log(n)).

Why? You need to go through each of the n nodes to insert it into the tree. Now to insert one node it would take log(n) comparisons.

So the overall time complexity to insert n nodes in a binary search tree would be O(n*log(n))

Answer 2

It takes O(log n) time to insert one node into a balanced binary search tree, so n nodes can be inserted to build a tree in O(n log n) time.

It remains to be shown that there isn't a better way to build the tree - for example, it also takes O(log n) time to insert an element into a heap, but there is a cleverer algorithm which builds a heap of size n in O(n) time. However, Ω(n log n) is a lower bound for any comparison-sorting algorithm, so there cannot be an asymptotically faster way to build a BST, because you can do a comparison sort by building a BST and then traversing it in order.