Delete operation in binary search tree

We already discussed two of the three operations in binary search tree :- insert, find and delete. We already discussed insert & delete , so lets discuss delete:-

Delete is one of the tricky operation in binary search tree as we have to readjust the child/children of the node which is to be deleted. If the node doesn't have any child/children, than its an easy operation.

Since deletion is tricky & complicated, lot of programmers add a boolean field like isDeleted to the Node class and set that as true so that when we are doing operations like search/insert in BST, we simply check the field if(isDeleted){} , just ignore that field.

Advantage :- We do not need to disturb the way tree is organized/structured.
Disadvantage :- There will be lot of memory wastage as nodes will not be sent to garbage collector and will keep living in the memory.

So delete in binary search tree means 3 scenarios:-

1) The node to be deleted is a leaf (no children)
2) The node to be deleted has one children

3) The node to be deleted has two children

We will start implementing the delete function in Java using the above three scenarios.


Step 1:- We will start the delete function by finding the node which needs to be deleted:-

public boolean delete(int d){

Node current = root;

Node parent = root;

boolean leftChild = true;

while (current.d!=d){

parent = current;

if(current.d>d){

leftChild=true;

current=current.leftChild;

}else{

leftChild=false;

current=current.rightChild;

}

if(current==null)

return false;

}

Step 2:- We will implement the first scenario where the node to be deleted can be a leaf node with no children

if(current.leftChild==null && current.rightChild==null){

if(current==root)

root=null;

if(leftChild){

parent.leftChild=null;

}else{

parent.rightChild=null;

}

return true;

}

Step 3:- We will implement the second scenario where the node to be deleted can have one children

if(current.leftChild==null){

if(current==root)

root=null;

if(leftChild){

parent.leftChild=current.rightChild;

}else{

parent.rightChild=current.rightChild;

}

return true;

}

if(current.rightChild==null){

if(current==root)

root=null;

if(leftChild){

parent.leftChild=current.leftChild;

}else{

parent.rightChild=current.leftChild;

}

return true;

}

Step 4:- We will implement the third scenario where the node to be deleted can have two children

(a) Now the node to be deleted (we will refer this as X) has both left & right child. 
(b) We need to find to the node which will replace X. 
(c) X replacement has to be found from its own tree. By own tree, I mean its own tree to which X is the root/parent. Basically from its left/right children/grandchildren/great grand children etc.
(d) We will refer replacement for X as its successor. We can use the analogy that king successor has to be someone from his son/grandsons.
(e) We will use in-order successor finding algo for BST for this.


Two cents to note (as per inorder successor in BST):-
* Successor of a node will always be either right node or some left child node of right node. 
* Also, successor node will never ever have left child.

We will have two scenarios when deleting a node with two child nodes:-

Scenario 1 :-

Successor from getSuccessor method is right child of the node to be deleted. In this case, we will perform 2 operations:-

    (i) Delete the node and plugin the successor to the parent of the deleted node.
    (ii) Plugin deleted nodes left child to the successor as its left child. 

else // two children, so replace with inorder successor

{

// get successor of node to delete (current)

Node successor = getSuccessor(current);

// connect parent of current to successor instead

if(current == root)

root = successor;

else if(isLeftChild)

parent.leftChild = successor;

else

parent.rightChild = successor;

// connect successor to current’s left child

successor.leftChild = current.leftChild;

} // end else two children

// (successor cannot have a left child)

return true;

} // end delete()

Scenario 2:-

Successor from getSuccessor method is left descendant from the right child of the node to be deleted. In this case we will perform 4 operations:-

         (i) Plug the right child of the successor into the left child field of the successor's parent.
         (ii) Plug the right child of the node to be deleted into the right child field of the successor.
         (iii) Unplug the node to be deleted from its parent and plug/set this to the successor.
         (iv) Unplug the left child of the node to be deleted and plug it into/as left child of the successor.