Code works fine for the given test case but gives wrong ans for the only test case on submission.
CODE:
import java.util.;
import java.io.;
public class Main {
public static void main(String args[]) throws IOException {
Main mainObj = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t > 0) {
int n = Integer.parseInt(br.readLine());
String str[] = br.readLine().trim().split("\\s+");
int arr[] = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(str[i]);
}
Arrays.sort(arr);
BST bst = mainObj.new BST(arr);
int m = Integer.parseInt(br.readLine());
String rem[] = br.readLine().trim().split("\\s+");
// int rem[] = new int[m];
for(int i = 0; i < m; i++) {
bst.remove(Integer.parseInt(rem[i]));
}
bst.preOrder();
t--;
}
}
class BST {
class Node {
int data;
Node left;
Node right;
}
private Node root;
public BST(int arr[]) {
this.root = constructBST(arr, 0, arr.length - 1);
}
public Node constructBST(int arr[], int lo, int hi) {
if(lo > hi) {
return null;
}
int mid = (lo + hi) / 2;
Node nn = new Node();
nn.data = arr[mid];
nn.left = constructBST(arr, lo, mid-1);
nn.right = constructBST(arr, mid+1, hi);
return nn;
}
public void preOrder() {
this.preOrder(this.root);
}
private void preOrder(Node node) {
if(node == null)
return;
System.out.print(node.data + " ");
this.preOrder(node.left);
this.preOrder(node.right);
}
public void remove(int item) {
this.remove(this.root, null, false, item);
}
private void remove(Node node, Node parent, boolean isLeftChild, int item) {
// if(node == null)
// return;
if(item > node.data) {
this.remove(node.right, node, false, item);
}
else if(item < node.data) {
this.remove(node.left, node, true, item);
}
else {
if(node.left == null && node.right == null) {
if(isLeftChild)
parent.left = null;
else
parent.right = null;
}
else if(node.left == null && node.right != null) {
if(isLeftChild)
parent.left = node.right;
else
parent.right = node.right;
}
else if(node.left != null && node.right == null) {
if(isLeftChild)
parent.left = node.left;
else
parent.right = node.left;
}
else {
int max = this.max(node.left);
node.data = max;
this.remove(node.left, node, true, max);
}
}
}
private int max(Node node) {
if(node.right == null) {
return node.data;
}
return max(node.right);
}
}
}