CODEWITHSUNDEEP
binary-search-tree
darrrrUC
darrrrUC

Reputation: 311

Best vs average runtime on binary seach trees

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?

Upvotes: 0

Views: 68

Answers (1)

attaboy182
attaboy182

Reputation: 2079

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.

Upvotes: 1

Related Questions