The GATE Grind

GATE 2015 CS – Question 35

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

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

  1. $\Theta(\log n)$ for both insertion and deletion
  2. $\Theta(n)$ for both insertion and deletion
  3. $\Theta(n)$ for insertion and $\Theta(\log n)$ for deletion
  4. $\Theta(\log n)$ for insertion and $\Theta(n)$ for deletion

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\Theta(n)$ for both insertion and deletion

Explanation

A binary search tree is not guaranteed to be balanced. In the worst case it becomes a chain of $n$ nodes, so both finding the place to insert and finding the node to delete take $\Theta(n)$.