Java Program to Perform Deletion in Binary Search Tree

«
»
This is a Java Program to perform deletion in the binary search tree.

Here is the source code of the Java Program to Perform Deletion in a BST. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to delete elements from Binary Search Tree
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. class BSTNode
  6. {
  7.     BSTNode left, right;
  8.     int     data;
  9.  
  10.     public BSTNode()
  11.     {
  12.         left = null;
  13.         right = null;
  14.         data = 0;
  15.     }
  16.  
  17.     public BSTNode(int n)
  18.     {
  19.         left = null;
  20.         right = null;
  21.         data = n;
  22.     }
  23.  
  24.     public void setLeft(BSTNode n)
  25.     {
  26.         left = n;
  27.     }
  28.  
  29.     public void setRight(BSTNode n)
  30.     {
  31.         right = n;
  32.     }
  33.  
  34.     public BSTNode getLeft()
  35.     {
  36.         return left;
  37.     }
  38.  
  39.     public BSTNode getRight()
  40.     {
  41.         return right;
  42.     }
  43.  
  44.     public void setData(int d)
  45.     {
  46.         data = d;
  47.     }
  48.  
  49.     public int getData()
  50.     {
  51.         return data;
  52.     }
  53. }
  54.  
  55. class BSTree
  56. {
  57.     private BSTNode root;
  58.  
  59.     public BSTree()
  60.     {
  61.         root = null;
  62.     }
  63.  
  64.     public boolean isEmpty()
  65.     {
  66.         return root == null;
  67.     }
  68.  
  69.     public void insert(int data)
  70.     {
  71.         root = insert(root, data);
  72.     }
  73.  
  74.     private BSTNode insert(BSTNode node, int data)
  75.     {
  76.         if (node == null)
  77.             node = new BSTNode(data);
  78.         else
  79.         {
  80.             if (data <= node.getData())
  81.                 node.left = insert(node.left, data);
  82.             else
  83.                 node.right = insert(node.right, data);
  84.         }
  85.         return node;
  86.     }
  87.  
  88.     public void delete(int k)
  89.     {
  90.         if (isEmpty())
  91.             System.out.println("Tree Empty");
  92.         else if (search(k) == false)
  93.             System.out.println("Sorry " + k + " is not present");
  94.         else
  95.         {
  96.             root = delete(root, k);
  97.             System.out.println(k + " deleted from the tree");
  98.         }
  99.     }
  100.  
  101.     private BSTNode delete(BSTNode root, int k)
  102.     {
  103.         BSTNode p, p2, n;
  104.         if (root.getData() == k)
  105.         {
  106.             BSTNode lt, rt;
  107.             lt = root.getLeft();
  108.             rt = root.getRight();
  109.             if (lt == null && rt == null)
  110.                 return null;
  111.             else if (lt == null)
  112.             {
  113.                 p = rt;
  114.                 return p;
  115.             } else if (rt == null)
  116.             {
  117.                 p = lt;
  118.                 return p;
  119.             } else
  120.             {
  121.                 p2 = rt;
  122.                 p = rt;
  123.                 while (p.getLeft() != null)
  124.                     p = p.getLeft();
  125.                 p.setLeft(lt);
  126.                 return p2;
  127.             }
  128.         }
  129.         if (k < root.getData())
  130.         {
  131.             n = delete(root.getLeft(), k);
  132.             root.setLeft(n);
  133.         } else
  134.         {
  135.             n = delete(root.getRight(), k);
  136.             root.setRight(n);
  137.         }
  138.         return root;
  139.     }
  140.  
  141.     public boolean search(int val)
  142.     {
  143.         return search(root, val);
  144.     }
  145.  
  146.     private boolean search(BSTNode r, int val)
  147.     {
  148.         boolean found = false;
  149.         while ((r != null) && !found)
  150.         {
  151.             int rval = r.getData();
  152.             if (val < rval)
  153.                 r = r.getLeft();
  154.             else if (val > rval)
  155.                 r = r.getRight();
  156.             else
  157.             {
  158.                 found = true;
  159.                 break;
  160.             }
  161.             found = search(r, val);
  162.         }
  163.         return found;
  164.     }
  165.  
  166.     public void inorder()
  167.     {
  168.         inorder(root);
  169.     }
  170.  
  171.     private void inorder(BSTNode r)
  172.     {
  173.         if (r != null)
  174.         {
  175.             inorder(r.getLeft());
  176.             System.out.print(r.getData() + " ");
  177.             inorder(r.getRight());
  178.         }
  179.     }
  180.  
  181.     public void preorder()
  182.     {
  183.         preorder(root);
  184.     }
  185.  
  186.     private void preorder(BSTNode r)
  187.     {
  188.         if (r != null)
  189.         {
  190.             System.out.print(r.getData() + " ");
  191.             preorder(r.getLeft());
  192.             preorder(r.getRight());
  193.         }
  194.     }
  195.  
  196.     public void postorder()
  197.     {
  198.         postorder(root);
  199.     }
  200.  
  201.     private void postorder(BSTNode r)
  202.     {
  203.         if (r != null)
  204.         {
  205.             postorder(r.getLeft());
  206.             postorder(r.getRight());
  207.             System.out.print(r.getData() + " ");
  208.         }
  209.     }
  210. }
  211.  
  212. public class Deletion_BST
  213. {
  214.     public static void main(String[] args)
  215.     {
  216.         BSTree bst = new BSTree();
  217.         System.out.println("Binary Search Tree Deletion Test\n");
  218.  
  219.         Scanner sc = new Scanner(System.in);
  220.         Random random = new Random();
  221.         int n = 15;
  222.         for (int i = 0; i < n; i++)
  223.             bst.insert(Math.abs(random.nextInt(100)));
  224.         char ch;
  225.         do
  226.         {
  227.             System.out.print("\nPost order : ");
  228.             bst.postorder();
  229.             System.out.print("\nPre order  : ");
  230.             bst.preorder();
  231.             System.out.print("\nIn order   : ");
  232.             bst.inorder();
  233.  
  234.             System.out.println("Enter integer element to delete");
  235.             bst.delete(sc.nextInt());
  236.             System.out.println("Continue deleting? <y>/<n>");
  237.             ch = sc.next().charAt(0);
  238.         } while (ch == 'y' || ch == 'Y');
  239.         sc.close();
  240.     }
  241. }

Output:

advertisement
$ javac Deletion_BST.java
$ java Deletion_BST
 
Binary Search Tree Deletion Test
 
 
Post order : 17 11 22 26 24 41 46 52 54 42 86 85 74 72 23 
Pre order  : 23 22 11 17 72 42 41 24 26 54 52 46 74 85 86 
In order   : 11 17 22 23 24 26 41 42 46 52 54 72 74 85 86 
Enter integer element to delete
17
17 deleted from the tree
Continue deleting? <y>/<n>
y
 
Post order : 11 22 26 24 41 46 52 54 42 86 85 74 72 23 
Pre order  : 23 22 11 72 42 41 24 26 54 52 46 74 85 86 
In order   : 11 22 23 24 26 41 42 46 52 54 72 74 85 86 
Enter integer element to delete
23
23 deleted from the tree
Continue deleting? <y>/<n>
y
 
Post order : 11 22 26 24 41 46 52 54 42 86 85 74 72 
Pre order  : 72 42 41 24 22 11 26 54 52 46 74 85 86 
In order   : 11 22 24 26 41 42 46 52 54 72 74 85 86 
Enter integer element to delete
11
11 deleted from the tree
Continue deleting? <y>/<n>
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.