Java Program to delete a node from Binary Search Tree(BST)

      In previous post, discussed about leaf node and total node count of BST. In this post, we will see how to delete a node from binary search tree.

      There are three scenario which we may need to consider while deleting a node from Binary Tree.

• If node has no child(i.e leaf node)
• If node has one child.
• If node has two children.

1) If node has no child(i.e leaf node)

       It is easy and straight forward, Just We need to search the node and make it null.

Example:--

2) If node has one child

     If node have one children then we need to connect parent of removed node directly to child of the removed node.

Example:-

3)  If node has two children

     It is somewhat complicated to delete the node.  If it has two nodes, we need to connect parent of node to the leftmost node(minimum) of right sub tree or rightmost node(maximum) of left sub tree.

Example:--

Java Program to Delete the Node from a Binary Tree.

BSTDeleteNode.java

package com.test;

class Node {
     

     Integer data;
     Node leftChild;
     Node rightChild;
 
     public Node(Integer data) {
           this.data = data;
           leftChild = null;
           rightChild = null;
     }
}

public class BSTDeleteNode {
 
       Node root;

       Node deleteNode(Integer data) {
            return deleteNode(root, data);
       }
       Node deleteNode(Node node, Integer data) {
            if (node == null) 
                 return node;
            if (data < node.data) {
                 node.leftChild = deleteNode(node.leftChild, data);
            } else if(data > node.data) {
                 node.rightChild = deleteNode(node.rightChild, data);
            } else {
                //node with only one child or no child
                 if (node.leftChild == null) {
                       return node.rightChild;
                 } else if(node.rightChild == null) {
                       return node.leftChild;
                 }
                 //node with two children, smallest in the right subtree
                 node.data = minValue(node.rightChild);
   
                 node.rightChild = deleteNode(node.rightChild, node.data);
   
           }
  
           return node;
      }
 
      int minValue(Node root) {
            int minv = root.data;
            while (root.leftChild != null) {
                minv = root.leftChild.data;
                root = root.leftChild;
            }
            return minv;
       }
 

       /*  To Print the given Node data

       */
       void inorderRec() {
             inorderRec(root);
       }
 
       void inorderRec(Node root) {
             if (root != null) {
                  inorderRec(root.leftChild);
                  System.out.print(root.data + " ");
                  inorderRec(root.rightChild);
             }
        }
 
        public static void main(String[] args) {
  
                BSTDeleteNode tree = new BSTDeleteNode();
                tree.root = new Node(10);
                tree.root.leftChild = new Node(6);
                tree.root.rightChild = new Node(16);
                tree.root.leftChild.leftChild = new Node(4);
                tree.root.leftChild.rightChild = new Node(8);
                System.out.println("Printing node before delete,");
                tree.inorderRec();
                tree.deleteNode(16);      //delete node method
                System.out.println("");
                System.out.println("Printing node after delete,");
                tree.inorderRec();
       }
}

Output :-
Printing node before delete,
4 6 8 10 16
Printing  node after delete,
4 6 8 10



Related Post:--
1) Java Program to Count the number of nodes and leaf nodes of Binary Tree
2) Java Program to Reverse a Linked List using Recursion and Loops
3) How to Remove duplicates from ArrayList in Java
4) Java Program to Count Occurrence of Word in a Sentence
5) How to iterate the TreeMap in reverse order in Java