Binary Search Trees-Deletion

Question

In the case of Binary Search Trees why cannot we simply put the predecessor in place of the successor of a node in deletion case where a node is having two children?

Answer 1

We'd like to delete such a node with minimum amount of work and disruption to the structure of the tree.

Suppose we want to delete the node containing 6 from the following tree:

The standard solution is based on this idea: we leave the node containing 6 exactly where it is, but we get rid of the value 6 and find another value to store in the 6 node. This value is taken from a node below the 6s node, and it is that node that is actually removed from the tree.

Now, what value can we move into the vacated node and have a binary search tree? Well, here's how to figure it out. If we choose value X, then:

1. everything in the left subtree must be smaller than X.
2. everything in the right subtree must be bigger than X.

Let's suppose we're going to get X from the left subtree. (2) is guaranteed because everything in the left subtree is smaller than everything in the right subtree. What about (1)? If X is coming from the left subtree, (1) says that there is a unique choice for X - we must choose X to be the largest value in the left subtree. In our example, 3 is the largest value in the left subtree. So if we put 3 in the vacated node and delete it from its current position we will have a BST with 6 deleted.

The result is :

Answer 2

why cannot we simply put the predecessor in place of the successor of a node in deletion case where a node is having two children?

We can put both and it is not necessary to replace the deleted node with the inorder successor. This is because in either case, the general contract of a BST is maintained.

Case1. Replace the deleted node with the inorder successor. This is done by finding the leftmost node in the deleted node's right subtree.

Case2. Replace the deleted node with the inorder predecessor. This is done by finding the rightmost node in the deleted node's left subtree.

Note that both these cases will keep all the elements in the left subtree smaller and all elements in right subtree greater than the element that we have brought into the position of the deleted node.