How can you delete a node in Binary Search Tree?

• Tweet
• Email

• Tweet
• Email

Let x be the node that has to be deleted from a binary search tree T. So, to delete the node x, we can have three cases:

1. x has no children
2. x has one child
3. x has two children

Case 1: x has no children

Let us take the first case first. When x has no children the deletion is fairly trivial. Take an example of following tree:

Now, to delete node B, all you have to do is go to the parent of B, which is A, and change the right pointer to null.

Similarly, if B were the left child of A you could go to the parent of B and change the left pointer to null. So if the node that has to be delete is a leaf node its fairly straightforward.

Case 2: x has one child

If the node that you are trying to delete has only one child, the deletion process is similar to deleting a node from linked list. Look at the following example:

Here, we are deleting node A which has a child B. You can delete node A (pointed by x) by going to the parent of A and changing its left pointer point to B. This will not violate the binary search property because everything on the left of D is smaller than D.

Case 3: x has two children

Let D be the node we need to delete which has two children A and F.

If a node to be deleted has two children and let x is the reference that points to the node that has to be deleted then you need to follow the procedure below:

• Find the predecessor (or successor) of x, call it y.
• Remove the y ( note that y has only one child at most because it is the predecessor of x.
• Replace x with y and delete predecessor node.

To find the predecessor just to to the left subtree of node and keep going through all the right nodes of left subtree.

Node with value B is the predecessor for our example pointed by y. So, replace D (pointed by x) with B and delete the node pointed by y.

If the node pointed by y (B in figure) has left subtree then the right child pointer is updated to point to the subtree of B.

With these processes we can delete a node in Binary Search Tree.

If you find this article useful, you are welcome to comment, suggest and add value to the topic.

Tagged As: Algorithms and Data Structures, Binary Search Tree, Delete Node in BSD