Deletion in BST

Problem Statement: 
    Delete a given a Node from Binary Search Tree:

Fig: Binary Search Tree

 Solution : 

Deletion in a one of the basic operation in a Binary Search Tree.

It involves two steps

• Searching
• Deletion

Deletion is slightly tricky compared to other operations of the Tree and we need to take care of few number of cases depending on the structure of the tree. I am skipping the searching logic which you all are aware of. 

There exists 3 cases in case of deletion of a node.

1. Node to be deleted has no children.
2. Node to be deleted has one child.
3. Node to be deleted has two children.

Lets take up these case individually , with diagrams

1. Node to be deleted has no children

This case is pretty simple , not much of work is to be done here , in this case just point the parent of the node to be deleted, to NULL.

 if(isLeftChild)  
    parent.left=null;  
 else  
    parent.right=null;  

2. Node to be deleted has one child.

  In this case the node has either left or right child , we need to simply connect parent of the node to be to deleted to child of the node to be deleted.

2a. No left child of node to be deleted

 if(isLeftChild)  
      parent.left = current.right;  
 else  
     parent.right = current.right;  

Fig: 2a Left child is null of the node to be deleted

2b. No right child of node to be deleted

 if(isLeftChild)  
      parent.left=current.left;  
 else  
     parent.right=current.left;  

Fig 2b. Right child is null of the node to be deleted

   3. Node to be deleted has two children.

        This case is slightly complicated, here we replace the node to deleted with its in-order successor , but here a tricky case comes up when the inorder-successor is the right child of the node to be deleted.

    3a. Inorder Successor is right child of node to be deleted

 Node successor = (Node) getSuccessor(current);  
 successor.left=current.left;  
   if(isLeftChild)  
      parent.left=successor;  
   else  
      parent.right=successor;  

Fig 3a. Inorder successor of node to be deleted is right child

Concept: 

•       Make z's left subtree as y's (successor) left subtree.
•       point z's parent (p) to y.
  

 
3b.  Inorder Successor is not right child of node to be deleted

 Node successor = (Node) getSuccessor(current);  
 Node successorParent=getSuccessorParent(current);  
 successorParent.left= successor.right;  
      if(isLeftChild)  
           parent.left=successor;  
      else  
           parent.right=successor;  
      successor.left=current.left;  
      successor.right=current.right;  

3b.in-order successor of node to be deleted in not the right child

Concept:
'z' (to be deleted) has two children 'l' and 'r' and its successor is y (is not equal to r) lies in the sub-tree rooted at r.

• make right sub-tree of successor(y) as  left sub-tree of successor's parent
• then we replace successor(y) by the node to be deleted(z) , and point z's parent(p) to successor(y)
• make z's left -subtree as y's left- subtree and z's right -subtree as y's right -subtree.

Note: here we will actually change pointers to delete the node instead of copying the data from inorder successor to the node to be deleted, hence the code differs from some of the books that you might have read.
     

Please refer to full Source Code

Now lets get on to the floor and implement the code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

// ---------------------------------------- Delete Node in Tree ------------------------------ public boolean deleteNode(int val) { if(startnode==null) return false; Node current=startnode; Node parent=startnode; boolean isLeftChild=true; // Find the node Logic Starts Here while(current.data!=val){ parent=current; if(val <current.data){ isLeftChild=true; current = current.left; } else { isLeftChild=false; current =current.right; } if(current==null) return false; } //Node to be deleted found and stored in current //Case 1: No childs of current if(current.left == null && current.right == null) { if(current==startnode) startnode=null; else { if(isLeftChild) parent.left=null; else parent.right=null; } } // Case 2a: No left child else if(current.left == null ){ if(current==startnode) startnode=current.right; else{ if(isLeftChild) parent.left = current.right; else parent.right = current.right; } } //Case 2b: No right child else if(current.right == null){ if(current == startnode) startnode=current.left; else{ if(isLeftChild) parent.left=current.left; else parent.right=current.left; } } //Case 3 both children else { Node successor = (Node) getSuccessor(current); //Case 3a: Successor is right child of node to be deleted if(current.right==successor) { successor.left=current.left; if(current==startnode) startnode=successor; else { if(isLeftChild) parent.left=successor; else parent.right=successor; } } // Case 3b: Successor is not the right child of node to be deleted but in the right sub-tree else { Node successorParent=getSuccessorParent(current); successorParent.left= successor.right; if(current==startnode) startnode=successor; else { if(isLeftChild) parent.left=successor; else parent.right=successor; } successor.left=current.left; successor.right=current.right; } } return true; }

I hope i have made my points clear through the code given and explanation. Post your comments if have any query. Run the code in link given above on ideone.com to check the output of sample input.

Happy Coding !!! :)