In the ninth part you will extend the binary search tree in

In the ninth part, you will extend the binary search tree in the eighth part to support the deletion of a node. The deletion of a node is slightly trickier compared to the search and insert in the eighth part.

The deletion is straightforward if the node to be deleted has only one child. You make the parent of the node to be deleted point to that child. In this scenario, special attention must be paid only when the node to be deleted is the root

Deleting a node with two children requires some more work. In this case, you must find the minimum element in the right subtree of the node to be deleted. Then you insert that node in the place where the node to be deleted was. This process needs to be repeated to delete the minimum node that was just moved.

In either case, if the node to be deleted is the root, you must update the pointer to the root to point to the new root node.

Input format: This program takes a file name as argument from the command line. The file is either blank or contains successive lines of input. Each line contains a character, ’i’, ’s’, or ’d’, followed by a tab and an integer. For each line that starts with ’i’, your program should insert that number in the binary search tree if it is not already there. If the line starts with a ’s’, your program should search for that value. If the line starts with a ’d’, your program should delete that value from the tree.

Output format: For each line in the input file, your program should print the status/result of the operation. For insert and search, the output is the same as in the Eighth Part: For an insert operation, the program should print either “inserted” with a single space followed by a number, the height of the inserted node in the tree, or ”duplicate” if the value is already present in the tree. The height of the root node is 1. For a search, the program should either print ”present”, followed by the height of the node, or ”absent” based on the outcome of the search. For a delete, the program should print ”success” or ”fail” based on the whether the value was present or not. Again, as in the Eight Part, your program should print ”error” (and nothing else) if the file does not exist or for input lines with improper structure.

Example Execution: Lets assume we have a file filel.txt with the following contents: i 5 i 3 i 4 i 1 i 6 i 2 s 1 d 3 s 2 Executing the program in the following fashion should produce the output shown below: ninth file1.txt inserted 1 inserted 2 inserted 3 inserted 3 inserted 2 inserted 4 present 3 Success present 4

Solution

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class tree {
   static Tree root = null;
   static int count=0;
   public static void main(String[] args) throws FileNotFoundException, IOException {
       // TODO Auto-generated method stub
       boolean flag;
       File file = new File(\"C:/Users/anmamaha/Desktop/dummy.txt\");
       File outfile = new File(\"C:/Users/anmamaha/Desktop/output.txt\");
       //FileOutputStream fout = new FileOutputStream(outfile);
       FileWriter fout = new FileWriter(outfile);
       tree t = new tree();
       try (BufferedReader br = new BufferedReader(new FileReader(file))) {
       String line;
       while ((line = br.readLine()) != null) {
           //System.out.println(line);
           String linearray[] = line.split(\"\\t\");
           if(\"i\".equals(linearray[0]) ||\"I\".equals(linearray[0]) ){
               t.insert(Integer.parseInt(linearray[1]));
               count++;
               fout.write(\"Inserted \"+count + \"\ \");
           }
           else if(\"s\".equals(linearray[0]) || \"S\".equals(linearray[0])){
               flag = t.searchkey(root,Integer.parseInt(linearray[1]));
               int depth = t.getLevelUtil(root,Integer.parseInt(linearray[1]) , 1);
               if(flag == true){
                   fout.write(\"present \ \");
               }
               else
               {
                   fout.write(\"key not found \ \");
               }
           }
           else if(\"D\".equals(linearray[0]) || \"d\".equals(linearray[0])){
               t.deleteNode(root,Integer.parseInt(linearray[1]));
               fout.write(\"Success \ \");
           }
       }
       }
      
      
      

   }
   Tree insertRec(Tree root, int key) {
         

if (root == null) {
root = new Tree(key);
return root;
}

if (key < root.data)
root.left = insertRec(root.left, key);
else if (key > root.data)
root.right = insertRec(root.right, key);
return root;
}
void insert(int key) {
root = insertRec(root, key);
}   

public void deleteNode(Tree node, int data)
{
   Tree prev = node;
  
   while(prev.data != data && prev!=null)
   {
       if(prev.data>data)
       {
           prev= node;
           node = node.left;
       }
       else if(prev.data<data)
       {
           prev = node;
           node = node.right;
       }
       else
       {
           if(node.left==null && node.right==null)
           {
               if(prev.data>data)
                   prev.left=null;
               else
                   prev.right=null;
           }
          
       }
   }
}
   public boolean searchkey(Tree root,int key){
       boolean flag = false;
       while(root!=null){
           if(root.data>key)
               root = root.left;
           else if(root.data<key){
               root =root.right;
           }
           else
               flag = true;
       }
       return flag;
   }
  
   int getLevelUtil(Tree node, int data, int level)
{
if (node == null)
return 0;
  
if (node.data == data)
return level;
  
int downlevel = getLevelUtil(node.left, data, level + 1);
if (downlevel != 0)
return downlevel;
  
downlevel = getLevelUtil(node.right, data, level + 1);
return downlevel;
}
}

class Tree{
   Tree left;
   Tree right;
   int data;
  
   Tree(int data){
       this.left = null;
       this.right = null;
       this.data = data;
   }
}