Best vs average runtime on binary seach trees

Question

It is known that O((log n)) is the average timecomplexity for search, insert and deletion for a binary search tree, my question is if this is also the best case? If not what are the best cases?

Possible duplicate of [Search times for binary search tree](http://stackoverflow.com/questions/526718/search-times-for-binary-search-tree) — Bla..., Mar 15 '16 at 11:47
This might answer your question: http://stackoverflow.com/questions/526718/search-times-for-binary-search-tree — Bla..., Mar 15 '16 at 11:48

score 1 · Accepted Answer · answered Mar 15 '16 at 13:23

The best case, as is the case with other data structures, is O(1).

Two examples:

1.)The node that you're searching for is the root and that's the only element in the BST.

2.) In a left/right skewed tree, the node that you want to delete is at the root.

Best vs average runtime on binary seach trees

1 Answers1