Delete a node from BST

Given a Binary Search Tree (BST) and a node no ‘x’ , your task is to delete the node ‘x’ from the BST

Solution:

• If its a leaf node set null.
• If it has only one child then set parent to grandchild.
• If its has two children then find inOrder successor or predecessor of that node.

Algorithm:

1. If node is null then,
   1. return null
2. If node.data < key then,
   1. node.right = recursively call for right child
3. Else If node.data > key then,
   1. node.left = recursively call for left child
4. Else
   1. If node is left node then
      1. return null
   2. Else If node has only one child then,
      1. return child
   3. Else
      1. InOrderSuccessorNode = Get InOrder Successor node
      2. node.data = InOrderSuccessorNode.data
      3. node.right = recursively call for right child with InOrderSuccessorNode.data as key
5. Return node

Latest Source Code:
Github: BinarySearchTreeDeleteNode.java

Output:

   50       
  / \   
 /   \  
 30   70   
/ \ / \ 
20 40 60 80 
                
---------------------------------------------------------
After delete 50 : 
   60       
  / \   
 /   \  
 30   70   
/ \   \ 
20 40   80 
                
---------------------------------------------------------
After delete 20 : 
   60       
  / \   
 /   \  
 30   70   
  \   \ 
  40   80