What is the time complexity of deleting a node in a binary tree

Question

For deleting a node in the binary tree, we have to search the node. That is possible in minimum O(log N) and max O(N). Depending on the node, we have to rearrange the pointers. How do we calculate the time complexity of that.

Answer 1

That depends on how you're doing the deletion. The most common way involves finding the successor of the node, then replacing the node with that successor. This can be done in O(h), where h is the height of the tree. In the worst case this is O(n), but in a balanced tree is worst-case O(lg n).

Answer 2

Yes best case complexity is O(logn) (when perfectly balanced) and
worst case complexity is O(n)
1 - 2 - 3 - 4

But the main problem with BST deletion (Hibbard Deletion) is that It is not symmetric. After many insertion and deletion BST become less balance. Researchers proved that after sufficiently long number of random insert and delete height of the tree becomes sqrt(n) . so now every operation (search, insert, delete) will take sqrt(n) time which is not good compare to O(logn) .

This is very long standing(around 50 years) open problem to efficient symmetric delete for BST. for guaranteed balanced tree, we have to use RedBlack Tree etc.