NO, or else we could sort in o(n lg n) time by building a BST in o(n lg n)
time and then doing an in-order tree walk in O(n) time.
In case of skewed BST (worst case) : O(n2)
Inserting first element ; 0 comparison
Inserting second element : 1 comparison
Inserting nth element : n-1 comparisons
Total : O(n2) comparisons
In case of Balanced BST : O(nlogn)