# What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in order and then do an in order traversal .

So the steps will be :

1. Let the empty BST be $\phi$
2. Take each element of the array and insert into the BST $\phi$ so that after insertion the BST property of the tree still holds.
3. Do an inorder traversal of the BST.

So steps 1 is $O(1)$ and step 3 is $\Theta(n)$ . I want to find out the lower and upper bounds on step 2.

-
Hint:we will get upper bound while inserting at the deepest node and lower bound while inserting at the shallowest node.Note that BST's are not height balanced. –  Saurabh Aug 20 '12 at 7:35
It might be more appropriate to use cs.stackexchange.com for such questions. –  Karolis Juodelė Aug 20 '12 at 7:36

The upper bound is $1+2+\dots+n = \frac{n(n+1)}{2}$ operations as the upper bound of insertion into a tree of $m$ nodes is $m$. This bound is reached is your array is sorted already.
The lower bound is $\log(1)+\log(2)+\dots+\log(n) = \log(n!)$ as the lower bound of insertion into a tree of $m$ nodes is $\log m$.. By Stirling's approximation this is $\log (\sqrt{2 \pi n}(\frac{n}{e})^n) = \frac{1}{2}\log(2\pi n) + n(\log(n) - 1)$ which is $O(n\log n)$.
@Geek, yes. Notice that these are not the only ways to reach it though. $2^{n-1}$ out of $n!$ orderings of the array do, I think. –  Karolis Juodelė Aug 20 '12 at 10:09