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), insertion's worst-case time complexity is $O(n)$. This occurs when the tree becomes unbalanced, resembling a linked list, requiring traversal of all $n$ nodes.

Step 2: Deletion Complexity.
Worst-case deletion in a BST also takes $O(n)$ time. This is due to the need to traverse the entire tree and possibly restructure it.

Step 3: Conclusion.
Consequently, both insertion and deletion operations in a binary search tree have a worst-case time complexity of $O(n)$.