Question

In a binary search tree, the worst case time complexity of inserting and deleting a key is:

• A. $O(\log n)$ for insertion and $O(n)$ for deletion
• B. $O(n)$ for insertion and $O(\log n)$ for deletion
• C. $O(n)$ for insertion and $O(n)$ for deletion
• D. $O(\log n)$ for insertion and $O(n)$ for deletion

Hint:

For an unbalanced binary search tree, both insertion and deletion have a worst case time complexity of $O(n)$, where $n$ is the number of nodes.

Answer 1

The Correct Option is C

Step 1: Insertion Complexity.
In a binary search tree (BST), in the worst case, the tree can be unbalanced (e.g., resembling a linked list). In this case, inserting a key will require traversing through all $n$ nodes, making the worst case time complexity for insertion **$O(n)$**.

Step 2: Deletion Complexity.
Similarly, in the worst case, deletion involves traversing the entire tree and potentially restructuring it, which takes **$O(n)$** time.

Step 3: Conclusion.
Thus, the worst case time complexity for both insertion and deletion in a binary search tree is **$O(n)$**.