Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?

The time complexity of inserting an element into a binary search tree (BST) is proportional to the height $h$ of the tree, i.e., $O(h)$.

• In the best/average case (balanced BST), $h = O(\log n)$.

• In the worst case (skewed BST), where elements are inserted in strictly ascending or descending order, the height of the tree becomes $h = n$, resulting in a time complexity of $O(n)$.

Since an upper bound must account for the worst-case scenario across all binary search trees of $n$ nodes, the tightest upper bound is $O(n)$ (Option C).