The Gateway to Computer Science Excellence
+30 votes
2.4k views

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
in DS by Boss (30.8k points)
edited by | 2.4k views
0
skewed tree

Θ(n) for both insertion and deletion.

2 Answers

+35 votes
Best answer

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.

by Active (1.2k points)
edited by
+20
Delete operation worst case is O(n).

Is it because finding the element itself in the skewed tree will take O(n) time ?
+5
Not only finding the element,we might have to search for inorder predecessor or successor incase if the deleted node has 2 children ... In worst case for finding inorder predecessor or successor we might take O(n) time as we might in worst case travel height of tree approximately .. Anyway overall O(n) time only for deletion ..
+1
what is the complexity if tree  is given as balanced

O(logn) for both the cases?
+4

Yes @ Moin Mukhtar  The worst case time complexity of search and insert operations is O(h) where h is height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node which is logn. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).

https://stackoverflow.com/questions/4582251/what-is-the-time-complexity-of-deleting-a-node-in-a-binary-tree

0
yes correct
+2 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)

by Boss (36.5k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,231 comments
104,914 users