CareerCup

in average case, it is O(log n), but the worst case , it is O(n)

log(n)

Tree construction:
Worst: O(n^2)
Best: O(n log n)

Look-up
O(Height_Of_the_Tree)

from: <introduction of algorithm>
it's O(height)
insert, delete, find, previous, succ,
for balanced tree, like red-black tree, O(logN)
for un-balanced tree, O(n)

For unbalanced BSTs:
--------------------
Insertion - O(log n) for average time, O(n) for worst time
Deletion - O(log n) for average time, O(n) for worst time
Search / Lookup - O(log n) for average time, O(n) for worst time
PreOrder - O(n)
PostOrder - O(n)
InOrder - O(n)
BFS - O(n)
DFS - O(n)

For balanced BSTs:
--------------------
Insertion - O(log n) most of the time
Deletion - O(log n) most of the time
Search / Lookup - O(log n) most of the time
PreOrder - O(n)
PostOrder - O(n)
InOrder - O(n)
BFS - O(n)
DFS - O(n)

For skewed(degenerate or BSTs like linked lists) BSTs:
------------------------------------------------------
Insertion - O(n) always
Deletion - O(n) always
Search / Lookup - O(n) always
PreOrder - O(n)
PostOrder - O(n)
InOrder - O(n)
BFS - O(n)
DFS - O(n)