import java.util.Iterator;
import java.util.LinkedList;

class Node<T>
{
    T value;
    Node<T> right;
    Node<T> left;
    Node<T> parent;

    Node(T value)
    {
        this.value = value;
        right = left= parent = null;
    }
}

public class MyTreeSet<T extends Comparable<T> > {
    private Node<T> root = null;
    private int treeSize = 0;

    public int size()
    {
        return treeSize;
    }

    public boolean add(T value)
    {
        Node<T> next = root;
        Node<T> parent = null;
        int diff;

        // Look to see if the Item is already in the Tree
        while(next != null)
        {
            parent = next;
            diff = value.compareTo(next.value);
            if (diff == 0) // found match and can't add ... must be unique
                return false;
            else if (diff > 0 )
                next = next.right;
            else
                next = next.left;
        }

        // Couldn't be found ... need to insert it.
        Node<T> newNode = new Node<T>(value);
        treeSize += 1;

        if (parent == null)
            root = newNode; // Must be the first Node
        else
        {
            // Create the parent, left/right links

            newNode.parent = parent;
            diff = value.compareTo(parent.value);
            if (diff > 0)
                parent.right = newNode;
            else
                parent.left = newNode;
        }

        return true;
    }

    public boolean contains(T value)
    {
        Node<T> next = root;
        int diff;

        while(next != null)
        {
            diff = value.compareTo(next.value);
            if (diff == 0) // found match
                return true;
            else if (diff > 0 )
                next = next.right;
            else
                next = next.left;
        }
        return false;
    }

    public Iterator<T> iterator()
    {
        return new MyIterator();
    }

    /******* Inner class Iterator *****/
    class MyIterator implements Iterator<T>
    {
        private Node<T> nextNode = null;

        MyIterator()
        {
            // Get the first node in the list
            nextNode = root;
            if (nextNode != null)
                goDownLeftLinks();
        }

        private void goDownLeftLinks()
        {
            while (nextNode.left != null)
                nextNode = nextNode.left;
        }
        private void moveToNext()
        {
            if (nextNode == null) return; // must be done
            if (nextNode.right != null)
            {
                // Need to follow the tree on the right
                nextNode = nextNode.right;
                goDownLeftLinks();
            }
            else
            {
                // We have already processed the left subtree, and there is no right tree.
                // We want to move up to find a parent where our nextNode is the left child
                // of the parent.  Note that nextNode has to be either a left or a right child.
                // So we keep climbing as long as nextNode is a right child.

                Node<T> parent = nextNode.parent;
                while (parent != null && nextNode == parent.right)
                {
                    nextNode = parent;
                    parent = nextNode.parent;
                }
                // if nextNode is null, then we are done.
                nextNode = parent;
            }
        }


        @Override
        public boolean hasNext() {
            if (nextNode== null)
                return false;
            return true;
        }

        @Override
        public T next() {
            T value = nextNode.value;
            moveToNext();
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Iterator.remove not implemented");

        }

    }
    // ******************  End of Inner class for Iterator