How to delete node in a Binary Search Tree

You must be wondering what makes this so hard, just chuck a node and that’s it. Well, not that easy..not that easy. The major issue is to delete a node in such a way that the property of Binary Search Tree is also preserved.

Let’s dive straight and understand what makes a normal ‘Binary Tree’ a ‘Binary Search Tree’.

A Binary Search Tree is a tree, where, for a node(A) the value of it’s left child(L) is smaller than the value of node(A) and the value of right child(R) is greater than the value of node(A).

So when we delete a node, we ought to preserve this same property, let’s take a vague example:

example

As you can see here, after chucking node 6, we have a lot of options, but bottom one doesn’t give us a Binary Search Tree, whereas the right one is a Binary Search Tree. The main property that we have to preserve is: “Every node on the left should be smaller than the parent node and every node on the right should be greater than the parent node. The bottom Binary Tree is a possible joint but is not a valid Binary Search Tree.

Apart from this we can run into two types of ‘to be deleted nodes’:

1: it's a node with only one child, handling this is easy.

2: it's a node with two children, handling this is relatively hard.

Before saying anything, I want to make a claim, by the end of this I promise that you’ll successfully understand how to delete a node plus how not to delete a node. With little practice you’ll nail this famous interview problem like a D.S.A. Monkey. Haha.

So here we go,

First things first, let’s search for the node that we want to delete, there are two ways to do that, either iteratively or by using recursion. I’ll use recursion because it’s more intuitive.

searching our node

Well, this is how we search our node, but we can tweak this function a little and as soon as we find our required node we can simply pass it to our reConnect() function which will make new connections(i.e. delete the required node).

tweaked form of search function

In deleteNode() function as soon as we’re finding our node, we’re passing it to the reconnect() fun. The structuring of deleteNode() fun is such that the reconnected node will be passed back to it’s parent node.

Let’s understand the magic behind reconnect() , if we want to delete a node there could be 2 major possibilities:

1. Our node to be deleted has only one child.
2. Our node to be deleted has two children.

handling case 1 : 
1> it has right child: then we can return right child
2> it has left child: then we can return left child.
handling case 2: 
1> The idea behind a B.S.T. is that every node on the left is smaller and every node on the right is greater. What we can do is find the left most node for the right child and then attach our left child to that left most node. It won't destroy the structuring of our binary search tree, let's understand from an example. 
       5
     /   \
    3     6
   / \ 
  2   4
   \
    1

in this binary search tree, if we have to remove node 3, which has two children, we can simply find the left most node of node 4and then attach node 2to it’s left. This is the hack, as the relative order of tree will also be preserved and the required node will also be deleted.

after deletion: 
       5
     /   \
    4    6
   / 
  2   
   \
    1

reconnect() fun

findLeftMost() find the leftmost node and returns it.

By gluing all these pieces together we can get our final answer:

final solution

final solution

Hope you liked this, give me a follow if you would love to read more from me. Till then, good bye. I’ll see you next week.