What is the time complexity of inserting into a balanced binary search tree (e.g., AVL or Red-Black) for n elements?

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

Answer: (C)

In a balanced binary search tree, the time to insert is determined by the length of the path from the root to the spot where the new key goes. Balancing keeps the height of the tree small relative to the number of nodes. For n elements, the height is proportional to log n. Insertion involves walking down that path and performing a constant amount of work at each node (including possible rotations to rebalance), so the total work grows proportional to the height. Therefore the time complexity is O(log n).

For contrast, O(1) would mean constant time, which isn’t possible because you must traverse from the root to the correct leaf. O(log log n) is smaller than what the height can achieve in a tree with n nodes. O(n) would be the cost for an unbalanced tree in the worst case. The balancing guarantees tighten the bound to O(log n), with specific height guarantees like AVL’s height ≤ ~1.44 log2(n+2) and red-black trees’ height ≤ 2 log2(n+1).