import java.util.Scanner;
public class Binary_Search_tree {
private class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
private Node root;
public void display() {
this.display(this.root);
}
private 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 void InRange(int a, int b) {
this.InRange(a, b, this.root);
}
private void InRange(int a, int b, Node node) {
if (node == null) {
return;
}
InRange(a, b, node.left);
if (node.data <= b && node.data >= a) {
System.out.print(node.data + " ");
}
InRange(a, b, node.right);
return;
}
public void Delete(int val) {
this.Delete(this.root, val);
}
private Node Delete(Node node, int val) {
if(node ==null)
return null;
if(val<node.data)
{
node.left= Delete(node.left, val);
}
else if(val>node.data)
{
node.right= Delete(node.right, val);
}
else //node.data==val
{
//LEAF NODE
if(node.left==null && node.right==null)
{
node=null;
return node;
}
//1 CHILD NODE
else if(node.left==null || node.right==null)
{
if(node.left==null)
{
Node temp=node.right;
node.right=null;
node=temp;
return node;
}
if(node.right==null)
{
Node temp=node.left;
node.left=null;
node=temp;
return node;
}
}
// 2 CHILD NODE
else
{
Node x=node.right;
if(x.left!=null)
{
while(x.left!=null)
{
x=x.left;
}
}
Node temp=x;
Delete(x.data);
node.data=temp.data;
}
}
return node;
}
public void Preoder() {
this.Preoder(this.root);
}
private void Preoder(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
Preoder(node.left);
Preoder(node.right);
}
private Node insetr(Node root, int val) {
if (root == null) {
Node nn = new Node(val);
return nn;
}
if (val < root.data) {
root.left = insetr(root.left, val);
} else if (val > root.data) {
root.right = insetr(root.right, val);
}
return root;
}
public void Construct(int a[]) {
this.root = this.Construct(a, null);
}
private Node Construct(int a[], Node nn) {
for (int i = 0; i < a.length; i++) {
nn = insetr(nn, a[i]);
}
return nn;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tt = sc.nextInt();
for (int d = 0; d < tt; d++) {
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
a[i] = x;
}
Binary_Search_tree b = new Binary_Search_tree();
b.Construct(a);
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
b.Delete(x);
}
b.Preoder();
}
}
}
i think error is in main function. plz check !