What is the time complexity for insertion in a binary search tree (BST)?

The correct answer regarding the time complexity for insertion in a binary search tree (BST) is related to the height of the tree, denoted as O(h).

When performing an insertion operation in a BST, the algorithm first compares the value being inserted with the current node's value, then either moves to the left or right child, continuing this process until the correct position for the new node is found. The height of the tree determines how many comparisons (or levels) the algorithm will have to traverse to find the appropriate insertion point.

In a balanced binary search tree, the height (h) is logarithmic with respect to the number of nodes (n), so insertion can be O(log n). However, if the tree is unbalanced (for example, if it resembles a linked list), the height can be linear, which results in O(n) time complexity for insertion. Thus, the complexity is generally expressed in relation to the height of the tree to capture both cases. Given that h can vary, stating the complexity as O(h) is both accurate and informative.

Understanding the structural nature of a BST is key here; specifically, how well-balanced the tree is can significantly affect performance. Therefore, stating the complexity as O(h) accurately reflects