We consider a variant of binary search trees in which $left(n) ≤ n < right(n)$ and this for any node $n$ of the tree.

Given two binary search trees $A$ and $B$, we are interested in removing from the tree $B$ all the elements that are common to $A$.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

 
 
 
 typedef struct Tree Tree;

struct Tree 
{
  Tree * left, * right;
  int element;
};
/*
typedef struct  node 
{ 
	int data;
	struct node *left, *right;
} *BST;
 */
  typedef  Tree *BST;


Tree *make_empty(Tree *t)
{
  if (t != NULL)
  {
    make_empty(t->left);
    make_empty(t->right);
    free(t);
  }

  return NULL;
}

Tree *find_min(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->left == NULL)
  {
    return t;
  }
  else
  {
    return find_min(t->left);
  }
}

Tree *find_max(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->right == NULL)
  {
    return t;
  }
  else
  {
    return find_max(t->right);
  }
}

Tree *find(int elem, Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }

  if (elem < t->element)
  {
    return find(elem, t->left);
  }
  else if (elem > t->element)
  {
    return find(elem, t->right);
  }
  else
  {
    return t;
  }
}

//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.                 
Tree * insert(int value, Tree * t) 
{
  Tree * new_node;
    
  if (t == NULL) 
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL) 
    {
	    return t;
    }

    new_node->element = value;

	  new_node->left = new_node->right = NULL;
	  return new_node;
  }
  
  if (value < t->element) 
  {
    t->left = insert(value, t->left);
  } 
  else if (value > t->element) 
  {
	  t->right = insert(value, t->right);
  } 
  else 
  { 
    //duplicate, ignore it
	  return t;
  }
  return t;
}

Tree * delete(int value, Tree * t) 
{
  //Deletes node from the tree
  // Return a pointer to the resulting tree
  Tree * x;
  Tree *tmp_cell;
  
  if (t==NULL) return NULL;
  
  if (value < t->element) 
  {
    t->left = delete(value, t->left);
  } 
  else if (value > t->element) 
  {
	  t->right = delete(value, t->right);
  } 
  else if (t->left && t->right)
  {
    tmp_cell = find_min(t->right);
    t->element = tmp_cell->element;
    t->right = delete(t->element, t->right);
  }
  else
  { 
    tmp_cell = t;
    if (t->left == NULL)
      t = t->right;
    else if (t->right == NULL)
      t = t->left;
    free(tmp_cell);
  }

  return t;
}


//printing tree in ascii

typedef struct asciinode_struct asciinode;

struct asciinode_struct
{
  asciinode * left, * right;

  //length of the edge from this node to its children
  int edge_length; 
    
  int height;      

  int lablen;

  //-1=I am left, 0=I am root, 1=right   
  int parent_dir;   
                         
  //max supported unit32 in dec, 10 digits max
  char label[11];  
};


#define MAX_HEIGHT 1000
int lprofile[MAX_HEIGHT];
int rprofile[MAX_HEIGHT];
#define INFINITY (1<<20)

//adjust gap between left and right nodes
int gap = 3;  

//used for printing next node in the same level, 
//this is the x coordinate of the next char printed
int print_next;    

int MIN (int X, int Y)  
{
  return ((X) < (Y)) ? (X) : (Y);
}

int MAX (int X, int Y)  
{
  return ((X) > (Y)) ? (X) : (Y);
}

asciinode * build_ascii_tree_recursive(Tree * t) 
{
  asciinode * node;
  
  if (t == NULL) return NULL;

  node = malloc(sizeof(asciinode));
  node->left = build_ascii_tree_recursive(t->left);
  node->right = build_ascii_tree_recursive(t->right);
  
  if (node->left != NULL) 
  {
    node->left->parent_dir = -1;
  }

  if (node->right != NULL) 
  {
    node->right->parent_dir = 1;
  }

  sprintf(node->label, "%d", t->element);
  node->lablen = strlen(node->label);

  return node;
}


//Copy the tree into the ascii node structre
asciinode * build_ascii_tree(Tree * t) 
{
  asciinode *node;
  if (t == NULL) return NULL;
  node = build_ascii_tree_recursive(t);
  node->parent_dir = 0;
  return node;
}

//Free all the nodes of the given tree
void free_ascii_tree(asciinode *node) 
{
  if (node == NULL) return;
  free_ascii_tree(node->left);
  free_ascii_tree(node->right);
  free(node);
}

//The following function fills in the lprofile array for the given tree.
//It assumes that the center of the label of the root of this tree
//is located at a position (x,y).  It assumes that the edge_length
//fields have been computed for this tree.
void compute_lprofile(asciinode *node, int x, int y) 
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
  if (node->left != NULL) 
  {
	  for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) 
    {
	    lprofile[y+i] = MIN(lprofile[y+i], x-i);
    }
  }
  compute_lprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
  compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

void compute_rprofile(asciinode *node, int x, int y) 
{
  int i, notleft;
  if (node == NULL) return;
  notleft = (node->parent_dir != -1);
  rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
  if (node->right != NULL) 
  {
	  for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) 
    {
	    rprofile[y+i] = MAX(rprofile[y+i], x+i);
    }
  }
  compute_rprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
  compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

//This function fills in the edge_length and 
//height fields of the specified tree
void compute_edge_lengths(asciinode *node) 
{
  int h, hmin, i, delta;
  if (node == NULL) return;
  compute_edge_lengths(node->left);
  compute_edge_lengths(node->right);

  /* first fill in the edge_length of node */
  if (node->right == NULL && node->left == NULL) 
  {
	  node->edge_length = 0;
  } 
  else 
  {
    if (node->left != NULL) 
    {
	    for (i=0; i<node->left->height && i < MAX_HEIGHT; i++) 
      {
		    rprofile[i] = -INFINITY;
	    }
	    compute_rprofile(node->left, 0, 0);
	    hmin = node->left->height;
    } 
    else 
    {
	    hmin = 0;
    }
	  if (node->right != NULL) 
    {
	    for (i=0; i<node->right->height && i < MAX_HEIGHT; i++) 
      {
		    lprofile[i] = INFINITY;
	    }
	    compute_lprofile(node->right, 0, 0);
	    hmin = MIN(node->right->height, hmin);
    } 
    else 
    {
	    hmin = 0;
    }
	  delta = 4;
	  for (i=0; i<hmin; i++) 
    {
	    delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
    }
	  
    //If the node has two children of height 1, then we allow the
    //two leaves to be within 1, instead of 2 
	  if (((node->left != NULL && node->left->height == 1) ||
	      (node->right != NULL && node->right->height == 1))&&delta>4) 
    {
      delta--;
    }
	    
    node->edge_length = ((delta+1)/2) - 1;
  }

  //now fill in the height of node
  h = 1;
  if (node->left != NULL) 
  {
	  h = MAX(node->left->height + node->edge_length + 1, h);
  }
  if (node->right != NULL) 
  {
	  h = MAX(node->right->height + node->edge_length + 1, h);
  }
  node->height = h;
}

//This function prints the given level of the given tree, assuming
//that the node has the given x cordinate.
void print_level(asciinode *node, int x, int level) 
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  if (level == 0) 
  {
	  for (i=0; i<(x-print_next-((node->lablen-isleft)/2)); i++) 
    {
	    printf(" ");
    }
	  print_next += i;
	  printf("%s", node->label);
	  print_next += node->lablen;
  } 
  else if (node->edge_length >= level) 
  {
	  if (node->left != NULL) 
    {
	    for (i=0; i<(x-print_next-(level)); i++) 
      {
		    printf(" ");
	    }
	    print_next += i;
	    printf("/");
	    print_next++;
    }
	  if (node->right != NULL) 
    {
	    for (i=0; i<(x-print_next+(level)); i++) 
      {
		    printf(" ");
	    }
	    print_next += i;
	    printf("\\");
	    print_next++;
    }
  } 
  else 
  {
	  print_level(node->left, 
                x-node->edge_length-1, 
                level-node->edge_length-1);
	  print_level(node->right, 
                x+node->edge_length+1, 
                level-node->edge_length-1);
  }
}

//prints ascii tree for given Tree structure
void print_ascii_tree(Tree * t) 
{
  asciinode *proot;
  int xmin, i;
  if (t == NULL) return;
  proot = build_ascii_tree(t);
  compute_edge_lengths(proot);
  for (i=0; i<proot->height && i < MAX_HEIGHT; i++) 
  {
	  lprofile[i] = INFINITY;
  }
  compute_lprofile(proot, 0, 0);
  xmin = 0;
  for (i = 0; i < proot->height && i < MAX_HEIGHT; i++) 
  {
	  xmin = MIN(xmin, lprofile[i]);
  }
  for (i = 0; i < proot->height; i++) 
  {
	  print_next = 0;
	  print_level(proot, -xmin, i);
	  printf("\n");
  }
  if (proot->height >= MAX_HEIGHT) 
  {
	  printf("(This tree is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT);
  }
  free_ascii_tree(proot); 
}


void print(BST B)
{
    print_ascii_tree(B);
}

int isEmptyBST(BST B) 
{
	return(B == NULL);
}
/*


int supprimer(ABR *pA, int Elt)
{
	if (arbre_vide(*pA)) 
		return 0;
	if ((*pA)->racine == Elt) 
		enlever_racine(pA);
	else
		if ((*pA)->racine > Elt) 
			supprimer(&((*pA)->SAG),Elt);
		else 
			supprimer(&((*pA)->SAD),Elt);
	return 1;
}





*/

 


void delete_root(BST *B)
{
	BST C, D;
 
	if( (*B)->left == (*B)->right &&  (*B)->right==NULL)  
	{
		C=*B;
		free(C);
		*B=NULL;
	}
	else
		if((*B)->right==NULL)
		{
			C=(*B);
			*B=(*B)->left;
			free(C);
		}
		else
			if((*B)->left==NULL)
			{
				C=(*B);
				*B=(*B)->right;
				free(C);
			}
			else // find the max on the right
			{
				C=(*B)->right;
				if(C->left==NULL)  
				{
					(*B)->right=C->right;
					(*B)->element=C->element;
					free(C);
				}
				else
				{
					while(C->left!=NULL)
					{
						D=C;
						C=C->left;
					}
					(*B)->element=C->element;
					D->left=C->right;
					free(C);

				}
			}
 
}



int belong(BST A, int Elt)
{
	if (isEmptyBST(A)) return 0;
	else if (A->element == Elt) return 1;
	else if (A->element > Elt) return belong(A->left,Elt);
	return belong(A->right,Elt);
}


void eliminate_in_commun(BST A, BST *B)
{
	if (*B)
	{
	  //  print(*B);
		if (belong(A,(*B)->element))
		{ 
			delete_root(B);
			eliminate_in_commun(A,B);
		}
		else
		{
		    eliminate_in_commun(A,&((*B)->left));
		    eliminate_in_commun(A,&((*B)->right));
		}
		
	}
}



void insert_BST(BST *B, int Elt)
{
	if (isEmptyBST(*B))
	{
		*B = (BST) malloc(sizeof(Tree));
		(*B)->element=Elt;
		(*B)->left=(*B)->right=NULL;
	}
	else 
		if ((*B)->element >= Elt) 
			insert_BST(&((*B)->left),Elt);
		else 
				insert_BST(&((*B)->right),Elt);
} 

 
void inorder(BST B)
{
    if(B)
    {
        
        inorder(B->left);
        printf("%d ",B->element);
        inorder(B->right);
    }
}


void preorder(BST B)
{
    if(B)
    {
        printf("%d ",B->element);
        preorder(B->left);
        preorder(B->right);
    }
}


void postorder(BST B)
{
    if(B)
    {
        postorder(B->left);
        postorder(B->right);
        printf("%d ",B->element);
    }
}


int main()
{
	BST A, B;
	int n1, n2, i, nb;
	int tests;
	scanf("%d",&tests);
	while(tests--)
	{
	    A=NULL;
	    B=NULL;
	    
	    
	    scanf("%d",&n1);
	    for(i=0; i<n1; i++)
	    {
	       scanf("%d",&nb);
	       insert_BST(&A,nb);
	    }
	    
	    scanf("%d",&n2);
	    for(i=0; i<n2; i++)
	    {
	       scanf("%d",&nb);
	       insert_BST(&B,nb);
	    }
	   
 
 
	    
	    eliminate_in_commun(A,&B);
	      
	   
	    
	    inorder(B);  printf("\n");  
 preorder(B);  printf("\n");  
 postorder(B);  printf("\n");  
	    
	    printf("\n");
	}

 
	return 0;
}