// Implements a BST with TreeNode nodes.

import java.util.Stack;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyTreeSet
      implements Iterable
{
  private TreeNode root;  // holds the root of this BST
  
  // Constructor: creates an empty BST.
  public MyTreeSet()
  {
    root = null;  
  }

  // Returns true if this BST contains value; otherwise returns false.
  public boolean contains(Object value)
  {
    return contains(root, value);
  }

  // Adds value to this BST, unless this tree already holds value.
  // Returns true if value has been added; otherwise returns false.
  public boolean add(Object value)
  {
    if (contains(value))
      return false;
    root = add(root, value);
    return true;
  }

  // Removes value from this BST.  Returns true if value has been
  // found and removed; otherwise returns false.
  public boolean remove(Object value)
  {
    if (!contains(value))
      return false;
    root = remove(root, value);
    return true;
  }

  // Returns a string representation of this BST.
  public String toString()
  {
    String str = toString(root);
    if (str.endsWith(", "))
      str = str.substring(0, str.length() - 2);
    return "[" + str + "]";
  }

  // Returns an iterator for this BST.
  public Iterator<Object> iterator()
  {
   return new MyTreeSetIterator(root);
  }

  //*************** Private helper methods: *********************

  // Returns true if the BST rooted at node contains value;
  // otherwise returns false (recursive version).
  private boolean contains(TreeNode node, Object value)
  {
    if (node == null)
      return false;
    else
    {
      int  diff = ((Comparable<Object>)value).compareTo(node.getValue());
      if (diff == 0)
        return true;
      else if (diff < 0)
        return contains(node.getLeft(), value);
      else // if (diff > 0)
        return contains(node.getRight(), value);
    }
  }

/*
  // Iterative version:
  private boolean contains(TreeNode node, Object value)
  {
    while (node != null)
    {
      int  diff = ((Comparable<Object>)value).compareTo(node.getValue());
      if (diff == 0)
        return true;
      else if (diff < 0)
        node = node.getLeft();
      else // if (diff > 0)
        node = node.getRight();
    }
    return false;
  }
*/

  // Adds value to the BST rooted at node. Returns the
  // root of the new tree. 
  // Precondition: the tree rooted at node does not contain value.
  private TreeNode add(TreeNode node, Object value)
  {
    if (node == null)
      node = new TreeNode(value);
    else
    {
      int  diff = ((Comparable<Object>)value).compareTo(node.getValue());
      if (diff < 0)
        node.setLeft(add(node.getLeft(), value));
      else // if (diff > 0)
        node.setRight(add(node.getRight(), value));
    }
    return node;
  }

  // Removes value from the BST rooted at node.
  // Returns the root of the new tree.
  // Precondition: the tree rooted at node contains value.
  private TreeNode remove(TreeNode node, Object value)
  {
  	//this needs to be written!!!!
      return null;
  }

  // Removes the root of the BST rooted at root
  // replacing it with the smallest node from the right subtree.
  // Returns the root of the new tree.
  private TreeNode removeRoot(TreeNode root)
  {
  	//this needs to be written!!!!!
     return null;
  }

  // Returns a string representation of the tree rooted at node.
  private String toString(TreeNode node)
  {
    if (node == null)
      return "";
    else
      return toString(node.getLeft()) + node.getValue() + ", " +
                          toString(node.getRight());
  }

 
 // Implements an Iterator for this tree.
  private class MyTreeSetIterator implements Iterator<Object>
  {
    private Stack<TreeNode> stk;

    public MyTreeSetIterator(TreeNode root)
    {
      stk = new Stack<TreeNode>();
      TreeNode node = root;
      while (node != null)
      {
        stk.push(node);
        node = node.getLeft();
      }
    }

    public boolean hasNext()
    {
      return !stk.isEmpty();
    }

    public Object next()
    {
      if (stk.isEmpty())
        throw new NoSuchElementException();
      TreeNode node = stk.pop();
      Object obj = node.getValue();
      node = node.getRight();
      while (node != null)
      {
        stk.push(node);
        node = node.getLeft();
      }
      return obj;
    }

    public void remove()
    {
      throw new UnsupportedOperationException();
    }
  }

  }