GATE CS 2015 Set 1 Q23 — Binary Search Trees

In a standard Binary Search Tree (BST) of $n$ nodes, the time complexity of search, insertion, and deletion operations is directly proportional to the height $h$ of the tree.

In the worst-case scenario, the BST is highly unbalanced (skewed), where each node has at most one child (resembling a singly linked list). In this case, the height of the tree is $h = \Theta(n)$.

• Insertion: To insert a new key, we must traverse from the root to find the appropriate empty spot. In a skewed tree, this traversal can go all the way to the deepest leaf, taking $\Theta(n)$ steps.
• Deletion: To delete a key, we first locate the node (which takes up to $\Theta(n)$ steps). If the node has two children, we must also find its inorder successor or predecessor, which can take another traversal. Thus, the overall worst-case complexity remains $\Theta(n)$.

Therefore, the worst-case complexities for both insertion and deletion are $\Theta(n)$, making Option B the correct choice.