Remove a node in binary search tree

Question

I am reading a book about removing a node from a binary search tree right now and the procedure described in the book seems unnecessarily complicated to me.

My question is specifically about removing a node that has both left and right subtree. In my opinion, node-to-remove should be replaced by the rightmost node in its left subtree or by its left node if its left subtree only has one node.

In case No.1, if we remove 40, it will be replaced by 30; in case No.2, if we remove 40, it will be replaced 35.

But in the book, it says the replacement should be found from node-to-remove's right subtree which could involve some complex manipulations.

Am I missing something here? Please point it out.

Answer 1

What you have pointed out is correct, the deleted node should be replace by either its in order successor which is the left most node in the right sub-tree or its in-order predecessor which is the right most node in the left sub-tree. This allows the tree to be traversed correctly. Most binary search tree data structures allow the deletion to be performed either way but in some cases special cases you might want to implement deletion such that the tree remains balanced.

More details and sample code is available on Wikipedia.

Answer 2

In case no.1 if you remove node 40 it will be replace by 50.

In case no.2 if you remove node 40 it will be replace by 50.

So basically when we delete any node that has 2 child then the removal should be as below. We go the right child of the node, and then extreme left of that child.

Below figures shown some example, how to delete a node from binary search tree. This is also taken from one book, but it is clearly explained.