import java.util.*;

import cs_1c.Traverser;

public class FHlazySearchTree<E extends Comparable< ? super E > >
   implements Cloneable
{
   protected int mSize;
   protected int mSizeHard;
   protected FHlazySTNode<E> mRoot;

   public FHlazySearchTree() { clear(); }
   public boolean empty() { return (mSize == 0); }
   public int size() { return mSize; }
   public int sizeHard() {return mSizeHard;}
   public void clear() { mSize = 0; mRoot = null; mSizeHard = 0;}
   public int showHeight() { return findHeight(mRoot, -1); }
   public void collectGarbage() { collectGarbage(mRoot); }

   public E findMin()
   {
      if (mRoot == null)
         throw new NoSuchElementException();
      return findMin(mRoot).data;
   }

   public E findMax()
   {
      if (mRoot == null)
         throw new NoSuchElementException();
      return findMax(mRoot).data;
   }

   public E find( E x )
   {
      FHlazySTNode<E> resultNode;
      resultNode = find(mRoot, x);
      if (resultNode == null)
         throw new NoSuchElementException();
      return resultNode.data;
   }

   public boolean contains(E x)  { return find(mRoot, x) != null; }

   public boolean insert( E x )
   {
      int oldSize = mSize;
      mRoot = insert(mRoot, x);
      return (mSize != oldSize);
   }

   public boolean remove( E x )
   {
      int oldSize = mSize;
      mRoot = remove(mRoot, x);
      return (mSize != oldSize);
   }

   public < F extends Traverser<? super E > >
   void traverse(F func)
   {
      traverse(func, mRoot);
   }

   public Object clone() throws CloneNotSupportedException
   {
      FHlazySearchTree<E> newObject = (FHlazySearchTree<E>)super.clone();
      newObject.clear();  // can't point to other's data

      newObject.mRoot = cloneSubtree(mRoot);
      newObject.mSize = mSize;
      newObject.mSizeHard = mSizeHard;

      return newObject;
   }

   // private helper methods ----------------------------------------
   protected FHlazySTNode<E> findMin( FHlazySTNode<E> root )
   {
      if (root == null)
         return null;

      //Checks left nodes first
      FHlazySTNode<E> temp = findMin(root.lftChild);

      if (temp != null)
         return temp;

      if (!root.deleted)
         return root;

      //If left nodes are deleted, will check right nodes.
      return findMin(root.rtChild);
   }

   protected FHlazySTNode<E> findMax( FHlazySTNode<E> root )
   {
      if (root == null)
         return null;

      //Checks Right nodes first
      FHlazySTNode<E> temp = findMax(root.rtChild);

      if (temp != null)
         return temp;

      if (!root.deleted)
         return root;

      //If Right nodes are deleted, will check left nodes.
      return findMax(root.lftChild);
   }

   protected FHlazySTNode<E> insert( FHlazySTNode<E> root, E x )
   {
      int compareResult;  // avoid multiple calls to compareTo()

      if (root == null)
      {
         mSizeHard++;
         mSize++;
         return new FHlazySTNode<E>(x, null, null, false);
      }

      compareResult = x.compareTo(root.data);
      if ( compareResult < 0 )
         root.lftChild = insert(root.lftChild, x);
      else if ( compareResult > 0 )
         root.rtChild = insert(root.rtChild, x);

      if (root.deleted == true)
      {
         root.deleted = false;
         mSize++;
      }
      return root;
   }


   protected FHlazySTNode<E> remove( FHlazySTNode<E> root, E x  )
   {
      int compareResult;  // avoid multiple calls to compareTo()

      if (root == null)
         return null;

      compareResult = x.compareTo(root.data);
      if ( compareResult < 0 )
         root.lftChild = remove(root.lftChild, x);
      else if ( compareResult > 0 )
         root.rtChild = remove(root.rtChild, x);

      // found the node
      if (root.deleted == false && compareResult == 0)
      {
         root.deleted = true;
         mSize--;
      }
      return root;
   }

   protected void collectGarbage(FHlazySTNode<E> root)
   {
      if (root == null)
         return;

      collectGarbage(root.lftChild);

      if (root.deleted == true)
         removeHard(mRoot, root.data);

      collectGarbage(root.rtChild);

      if (root == mRoot && root.rtChild == null &&
            root.lftChild == null && root.deleted == true)
         clear();
   }

   private FHlazySTNode<E> removeHard( FHlazySTNode<E> root, E x)
   {
      int compareResult;  // avoid multiple calls to compareTo()

      if (root == null)
         return null;

      compareResult = x.compareTo(root.data);
      if ( compareResult < 0 )
         root.lftChild = removeHard(root.lftChild, x);
      else if ( compareResult > 0 )
         root.rtChild = removeHard(root.rtChild, x);

      // found the node
      else if (root.lftChild != null && root.rtChild != null)
      {
         root.deleted = findMinH(root.rtChild).deleted;
         root.data = findMinH(root.rtChild).data;
         root.rtChild = removeHard(root.rtChild, root.data);
      }
      else
      {
         root =
            (root.lftChild != null)? root.lftChild : root.rtChild;
         mSizeHard--;

         if (mRoot == root )
            clear();
      }
      return root;
   }

   protected FHlazySTNode<E> findMinH( FHlazySTNode<E> root )
   {
      if (root == null)
         return null;
      if (root.lftChild == null)
         return root;
      return findMinH(root.lftChild);
   }

   protected FHlazySTNode<E> findMaxH( FHlazySTNode<E> root )
   { //Not used currently, meant for AVL.
      if (root == null)
         return null;
      if (root.lftChild == null)
         return root;
      return findMaxH(root.lftChild);
   }

   protected <F extends Traverser<? super E>> //No Update Needed
   void traverse(F func, FHlazySTNode<E> treeNode)
   {
      if (treeNode == null)
         return;

      traverse(func, treeNode.lftChild);
      func.visit(treeNode.data);
      traverse(func, treeNode.rtChild);
   }

   protected FHlazySTNode<E> find( FHlazySTNode<E> root, E x )
   {
      int compareResult;  // avoid multiple calls to compareTo()

      if (root == null)
         return null;

      compareResult = x.compareTo(root.data);
      if (compareResult < 0)
         return find(root.lftChild, x);
      if (compareResult > 0)
         return find(root.rtChild, x);

      if (root.deleted == true)
         return null; // soft deleted

      return root;   // found
   }

   protected FHlazySTNode<E> cloneSubtree(FHlazySTNode<E> root)
   {
      FHlazySTNode<E> newNode;
      if (root == null)
         return null;

      // does not set myRoot which must be done by caller
      newNode = new FHlazySTNode<E>
      (
         root.data,
         cloneSubtree(root.lftChild),
         cloneSubtree(root.rtChild),
         root.deleted
      );
      return newNode;
   }

   protected int findHeight( FHlazySTNode<E> treeNode, int height )
   {
      int leftHeight, rightHeight;
      if (treeNode == null)
         return height;
      height++;
      leftHeight = findHeight(treeNode.lftChild, height);
      rightHeight = findHeight(treeNode.rtChild, height);
      return (leftHeight > rightHeight)? leftHeight : rightHeight;
   }
}


class FHlazySTNode<E extends Comparable< ? super E > >
{
   // use public access so the tree or other classes can access members
   public FHlazySTNode<E> lftChild, rtChild;
   public E data;
   public FHlazySTNode<E> myRoot;  // needed to test for certain error
   public boolean deleted;

   public FHlazySTNode( E d, FHlazySTNode<E> lft, FHlazySTNode<E> rt, boolean del )
   {
      lftChild = lft;
      rtChild = rt;
      data = d;
      deleted = del;
   }

   public FHlazySTNode()
   {
      this(null, null, null, false);
   }

   // function stubs -- for use only with AVL Trees when we extend
   public int getHeight() { return 0; }
   boolean setHeight(int height) { return true; }
}