THE CODE BELOW GAVE ME CORRECT OUTPUTS FOR ALL THE TEST CASES THAT I HAVE TRIED MYSELF AND ALSO FOR SAMPLE TEST CASE GIVEN. BUT ON SUBMISSION, NONE OF THE TEST CASES HAVE PASSED. PLEASE HELP ME TO FIGURE OUT WHAT IS THE PROBLEM.
import java.util.*;
public class Main
{
private class Node
{
int data;
Node left;
Node right;
}
private Node root;
public Main(ArrayList<Integer> arr)
{
this.root=construct(arr,0,arr.size()-1);
}
private Node construct(ArrayList<Integer> arr,int low,int high)
{
if(low>high)
return null;
int mid=(low+high)/2;
Node nn=new Node();
nn.data=arr.get(mid);
nn.left=construct(arr,low,mid-1);
nn.right=construct(arr,mid+1,high);
return nn;
}
public void preOrder(Node root)
{
if(root==null)
return;
System.out.print(root.data+" ");
preOrder(root.left);
preOrder(root.right);
}
public void deleteNode(int[] arr)
{
int data;
for(int i=0;i<arr.length;i++)
{
data=arr[i];
remove(data,this.root,this.root);
}
}
public void remove(int data,Node parent,Node node)
{
if(node==null)
return;
if(node.data==data)
{
if(node.left==null&&node.right==null) //no child
{
if(node==parent) //root node
this.root=null;
else
{
if(parent.left==node)
parent.left=null;
else
parent.right=null;
}
}
else if(node.left==null&&node.right!=null) //right exist
{
if(node==parent) //root node
this.root=parent.right;
else
{
if(parent.left==node)
parent.left=node.right;
else
parent.right=node.right;
}
}
else if(node.left!=null&&node.right==null) //left exist
{
if(node==parent) //root node
this.root=parent.left;
else
{
if(parent.left==node)
parent.left=node.left;
else
parent.right=node.left;
}
}
else //both exist
{
Node x=node;
Node temp=node.right;
while(temp.left!=null)
{
x=temp;
temp=temp.left;
}
node.data=temp.data;
if(x==node)
x.right=null;
else
x.left=null;
}
return;
}
remove(data,node,node.left);
remove(data,node,node.right);
}
public void display(Node node)
{
String str="";
if(node.left!=null)
str=str+node.left.data+"=>";
else
str=str+"END=>";
str=str+node.data;
if(node.right!=null)
str=str+"<=" + node.right.data;
else
str=str+"<=END";
System.out.println(str);
if(node.left!=null)
this.display(node.left);
if(node.right!=null)
this.display(node.right);
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
for(int i=1;i<=T;i++)
{
int n=sc.nextInt();
ArrayList<Integer> list=new ArrayList<>(n);
for(int j=0;j<n;j++)
list.add(sc.nextInt());
int p=sc.nextInt();
int a[]=new int[p];
for(int k=0;k<p;k++)
a[k]=sc.nextInt();
list.sort(null);
Main tree=new Main(list);;
tree.deleteNode(a);
}
}
}