Time complexity of deletion in binary search tree

Question

Assume the height of the BST is h. If we want to delete a node with two children, then what would be the time complexity of the process.

I know that in a normal binary tree, the time complexity for deletion is O(h); O(n) worst case and O(logn) best case. But since we are replacing the key of the deleting node by the minimum node of right sub tree of it, it will take more time to find the minimum key.

So does anybody know how to explain the time complexity in this situation?

Answer 1

Source Wikipedia :

Deletion

There are three possible cases to consider:

• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

• Deleting a node with one child: Remove the node and replace it with its child.

• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If you choose in-order successor of a node, as right sub tree is not NIL( Our present case is node has 2 children), then its in-order successor is node with least value in its right sub tree, which will have at a maximum of 1 sub tree, so deleting it would fall in one of first 2 cases.

Deleting a node with two children from a binary search tree. First the rightmost node in the left subtree, the inorder predecessor 6, is identified. Its value is copied into the node being deleted. The inorder predecessor can then be easily deleted because it has at most one child. The same method works symmetrically using the inorder successor labelled 9.

Consistently using the in-order successor or the in-order predecessor for every instance of the two-child case can lead to an unbalanced tree, so some implementations select one or the other at different times.

Runtime analysis:

Although this operation does not always traverse the tree down to a leaf, this is always a possibility; thus in the worst case it requires time proportional to the height of the tree. It does not require more even when the node has two children, since it still follows a single path and does not visit any node twice. Hence the pointer adjustments in all three cases need constant time.

Useful Links :

• http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
• http://cse.iitkgp.ac.in/~pb/algo-1-pb-10.pdf