edited by
10,323 views
47 votes
47 votes

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
edited by

3 Answers

Best answer
45 votes
45 votes

Option B, both happens when the BST is skewed.

What is a  Skewed Tree?

A binary tree which is dominated solely by left child nodes or right child nodes is called a skewed binary tree or more specifically left skewed binary tree or right skewed binary tree respectively.

edited by
4 votes
4 votes

binary search tree is not height balance tree . so it may be left skewed and right skewed . so insertion and deletion is become o(n)

–1 votes
–1 votes
Last time I checked Worst case was big oh not big theta

Examiner has given theta notation to confuse students

But, remember that we have to find worst case

forget the notation

in worst case, BST can be either left or right skewed

Worst case input to the algorithm would be Increasing order or decreasing order of elements.

Hence

linear line complexity in both insertion and deletion

 

THanks
Answer:

Related questions

25 votes
25 votes
3 answers
1
28 votes
28 votes
1 answer
2
makhdoom ghaya asked Feb 13, 2015
6,930 views
Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$.$$\begin{array}{|l|l|}\hline \text{Array index} & \text{1} & \text{2} & \text{3} & \...
23 votes
23 votes
4 answers
3
25 votes
25 votes
8 answers
4
go_editor asked Feb 14, 2015
7,256 views
While inserting the elements $71, 65, 84, 69, 67, 83$ in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is$65$$67$$69$$83$