import java.io.*;
class node
{
int data;
node left;
node right;
node(int item)
{
data=item;
left=null;
right=null;
}
}
class bstree
{
static node root=null,parent=null;;
static int count=0,no=0;
public static void main(String args[])
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int choice,value;
node temp=null,loc=null,prev=null;
String s;
try
{
do
{
System.out.print("\n\nMenu\n1.Insert a node\n2.Delete a node\n3.Exit\nEnter your choice : ");
choice=Integer.parseInt(br.readLine());
switch(choice)
{
case 1 : do
{
System.out.print("Enter the value to be inserted : ");
value=Integer.parseInt(br.readLine());
temp=new node(value);
loc=root;
prev=null;
no++;
if(loc==null)
root=temp;
else
{
count=2*count+2;
while(loc!=null)
{
prev=loc;
if(temp.data<loc.data)
loc=loc.left;
else
loc=loc.right;
}
if(temp.data<prev.data)
prev.left=temp;
else
prev.right=temp;
}
System.out.print("Do you wish to continue Insertion (y/n) ? : ");
s=br.readLine();
}
while(s.charAt(0)=='y'||s.charAt(0)=='Y'…
display();
break;
case 2 : System.out.print("Enter the value to be deleted : ");
value=Integer.parseInt(br.readLine());
loc=root;
prev=null;
boolean flag=false;
if(loc==null)
System.out.println("The tree is empty!");
else
{
while(loc!=null)
{
if(loc.data==value)
{
deletenode(loc,prev);
no--;
flag=true;
}
prev=loc;
if(value<loc.data)
loc=loc.left;
else
loc=loc.right;
}
if(flag==false)
System.out.println("The value not found in the tree!");
}
display();
break;
case 3 : break;
default: System.out.println("Wrong choice!");
break;
}
}
while(choice!=3);
}
catch(Exception e)
{
System.err.println("Error : "+e);
}
}
public static void deletenode(node delnode,node prev)
{
if(delnode.left==null&&delnode.right==nu…
{
if(delnode==root)
root=null;
else if(prev.left==delnode)
prev.left=null;
else
prev.right=null;
}
else if(delnode.left==null)
{
if(delnode==root)
root=delnode.right;
else if(prev.left==delnode)
prev.left=delnode.right;
else
prev.right=delnode.right;
}
else if(delnode.right==null)
{
if(delnode==root)
root=delnode.left;
else if(prev.left==delnode)
prev.left=delnode.left;
else
prev.right=delnode.left;
}
else
{
node successor=delnode.right;
if(successor.left!=null)
{
successor=inordersuccessor(successor);
parent.left=successor.right;
successor.right=parent;
successor.left=delnode.left;
}
else
successor.left=delnode.left;
if(delnode==root)
root=successor;
else if(prev.left==delnode)
prev.left=successor;
else
prev.right=successor;
}
}
public static node inordersuccessor(node loc)
{
while(loc.left!=null)
{
parent=loc;
loc=loc.left;
}
return loc;
}
public static void display()
{
node temp,loc=root;
int i,size=count+1,x=no;
if(loc==null)
System.out.println("The tree is empty!");
else
{
node[] arr=new node[size];
arr[0]=root;
for(i=1;i<size-1;i+=2)
{
temp=arr[(i-1)/2];
if(temp!=null&&temp.left!=null)
arr[i]=temp.left;
else
arr[i]=null;
if(temp!=null&&temp.right!=null)
arr[i+1]=temp.right;
}
System.out.println("The tree is now : ");
for(i=0;i<size;i++)
{
if(x==0)
break;
else
{
if(arr[i]==null)
System.out.print("-1 ");
else
{
System.out.print(arr[i].data+" ");
x--;
}
}
}
}
}
}