class IntSet21
{
// Constructive Set class, sets stored as ordered ADT trees
// Uses stack rather than recursion to print trees
// Includes breadth-first print method

 private Tree tree;

 public IntSet21()
 {
  tree=Tree.empty();
 }

 private IntSet21(Tree t)
 {
  tree=t;
 }

 public IntSet21 delete(int n)
 {
  return new IntSet21(delete(n,tree));
 }

 private static Tree delete(int n,Tree t)
 {
  if(t.isEmpty())
     return Tree.empty();
  else if(n<t.item())
     return Tree.make(t.item(),delete(n,t.left()),t.right());
  else if(n>t.item())
     return Tree.make(t.item(),t.left(),delete(n,t.right()));
  else if(t.left().isEmpty())
     return t.right();
  else if(t.right().isEmpty())
     return t.left();
  else
     {
      int m=rightmost(t.left());
      Tree newleft=removeRightmost(t.left());
      return Tree.make(m,newleft,t.right());
     }
 }

 private static int rightmost(Tree t)
 {
  if(t.right().isEmpty())
     return t.item();
  else
     return rightmost(t.right());
 }

 private static Tree removeRightmost(Tree t)
 {
  if(t.right().isEmpty())
     return t.left();
  else
     return Tree.make(t.item(),t.left(),removeRightmost(t.right()));
 }

 public IntSet21 add(int n)
 {
  return new IntSet21(add(n,tree));
 }

 private static Tree add(int n, Tree t)
 {
  if(t.isEmpty())
     return Tree.make(n,Tree.empty(),Tree.empty());
  else if(n==t.item())
     return t;
  else if(n<t.item())
     return Tree.make(t.item(),add(n,t.left()),t.right());
  else
     return Tree.make(t.item(),t.left(),add(n,t.right()));
 }

 public boolean member(int n)
 {
  return member(n,tree);
 }

 private static boolean member(int n,Tree t)
 {
  if(t.isEmpty())
     return false;
  else if(t.item()==n)
     return true;
  else if(n<t.item())
     return member(n,t.left());
  else
     return member(n,t.right());
 }

 public String toString()
 {
  if(tree.isEmpty())
     return "{}";
  else
     {
      Stack stack = new Stack();
      stack.push(tree);
      return "{"+toString(stack)+"}";
     }
 }

 private static String toString(Stack stack)
 {
  String str="";
  while(!stack.isEmpty())
     {
      Object next = stack.top();
      stack.pop();
      if(next instanceof Integer)
         {
          str+=next;
          if(!stack.isEmpty())
             str+=',';
         }
      else 
         {
          Tree t = (Tree)next;
          if(!t.right().isEmpty())
             stack.push(t.right());
          stack.push(new Integer(t.item()));
          if(!t.left().isEmpty())
             stack.push(t.left());
         }
     }
  return str;
 }

 public String breadthFirst()
 {
  if(tree.isEmpty())
     return "{}";
  else
     {
      Queue q = new Queue();
      q.join(tree);
      return "{"+breadthFirst(q)+"}";
     }
 }

 private static String breadthFirst(Queue q)
 {
  String str="";
  while(!q.isEmpty())
     {
      Tree t = (Tree)q.first();
      q.leave();
      if(!t.left().isEmpty())
         q.join(t.left());
      if(!t.right().isEmpty())
         q.join(t.right());
      str+=t.item();
      if(!q.isEmpty())
         str+=",";
     }
  return str;
 }

 public String treeString()
 {
  return tree.toString();
 }

}