# Best-Case Running Time For Binary Search Tree Insertion

The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:

The term best-case performance is used in computer science to describe the way of an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.

According to this definition, the best case running time for BST insertion should be $O(1)$ [consider that we are inserting to the root node]. But different resources says different things, some claim that it is $O(\log n)$ [perfect balanced tree] and some others claim that it is $O(1)$ which one should I believe?

• For any (reasonable) binary search tree implementation, the best-case insertion time is certainly $O(1)$ (for all sizes): all nodes are in the root's right subtree, the one to be inserted belong in the left.
• An optimal binary search tree implemenentation has worst-case insertion time in $\Theta(\log n)$; it is height-balanced (examples include AVL- and Red-Black-trees).