In a balanced binary search tree, what is the time complexity of search, insert, and delete operations in the worst case?

• A. O(n)
• B. O(log n)
• C. O(1)
• D. O(n log n)

Answer: (B)

The time for search, insert, and delete in a balanced binary search tree is driven by the height of the tree. In a balanced tree, the height grows only logarithmically with the number of nodes, so the longest path from the root to any node is O(log n). Each of these operations involves traversing a path from the root to the target location (or to where a new node is inserted or an existing one is removed) and possibly performing a small, constant amount of rebalancing along that path. Since the path length is the height, all three operations take O(log n) in the worst case. The balancing steps themselves don’t change this bound because their work per operation is constant. In an unbalanced tree, the height could degrade to O(n), but in a balanced tree it stays logarithmic, which is why the best answer is O(log n).