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 :
- Let the empty BST be $\phi$
- Take each element of the array and insert into the BST $\phi$ so that after insertion the BST property of the tree still holds.
- 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.