GATE CS 2015 Set 1 Q.33 (CS Q.23): Binary Trees, Binary Search Trees and Balanced Trees

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

$\Theta(\log n)$ for both insertion and deletion

$\Theta(n)$ for both insertion and deletion

$\Theta(n)$ for insertion and $\Theta(\log n)$ for deletion

$\Theta(\log n)$ for insertion and $\Theta(n)$ for deletion

Official answer and solution

Solution

Analyze the worst-case shape of a Binary Search Tree and the resulting search, insertion, and deletion times.

In an arbitrary (unbalanced) Binary Search Tree containing $n$ elements:

If keys are inserted in sorted (or reverse sorted) order, the BST degenerates into a linear chain (skewed tree) of depth $n$ .
Insertion: Finding the insertion position requires traversing down the skewed tree to the leaf position, taking $\Theta(n)$ comparisons in the worst case.
Deletion: Locating the node to delete and its in-order predecessor/successor requires traversing the path of length $n$ , also taking $\Theta(n)$ time in the worst case.

Thus, both insertion and deletion have a worst-case time complexity of $\Theta(n)$ (option B).

Final answer

Common trap

Assuming an AVL or self-balancing binary search tree where operations are $\Theta(\log n)$ , rather than an ordinary BST.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.