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
edited | 2.4k views
0
skewed tree

Θ(n) for both insertion and deletion.

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
+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

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)