Question

What is the time complexity of inserting an element into a balanced binary search tree?

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

Hint:

Balanced BSTs ensure $O(\log n)$ for operations by maintaining height constraints.

Answer 1

The Correct Option is A

In a balanced binary search tree (e.g., AVL or Red-Black tree):
- The height is $O(\log n)$ due to balancing properties.
- Insertion involves traversing from root to leaf to find the insertion point, which takes $O(\log n)$.
- After insertion, rebalancing (rotations) takes $O(\log n)$ in worst case.
Thus, total time complexity is $O(\log n)$.
Option (1) is correct.