import java.util.AbstractSet;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;
import java.util.SortedSet;


public class BinarySearchTree<T> extends AbstractSet<T> {
    private BinaryTreeNode<T> root;
    private int size;
    private Comparator<? super T> comparator;
    
    /**
     * Default constructor
     */
    public BinarySearchTree() {
        size = 0;
        root = null;
        comparator = null;
    } // end comnstructor
    
    /**
     * Constructor with Comparator paremeter
     * @param comparator Comparator for this tree
     */
    public BinarySearchTree(Comparator<T> comparator) {
        size = 0;
        root = null;
        this.comparator = comparator;
    } // end comnstructor
    
    /**
     * Root constructor
     * @param rootData data assigned to the root
     */
    public BinarySearchTree(T rootData) {
        size = 0;
        comparator = null;
        root = new BinaryTreeNode<T>(rootData);
    }
    
    /**
     * Return the size of the binary tree
     * @return the number of nodes in the tre
     */
    public int size() {
        return size;
    } // end size
    
    /**
     * Check for a leaf
     * @ return true if a leaf; false otherwise
     */
    public boolean isLeaf() {
        return root.isLeaf();
    }
   
    /**
     * Return the last (Maximum( value in the tree
     * @return the maximum value in the tree
     */
    public T last() {
        return getMax(root);
    }
    
    private T getMax(BinaryTreeNode<T> tree)  {
        if( tree == null ) throw new NoSuchElementException();
        if( tree.right == null ) return tree.data;
        return getMax(tree.right);
    }
    /**
     * Accessor for the root data
     * @return root data
     */
    public Object getData() {
        return root.data;
    }
    
    private BinarySearchTree(BinaryTreeNode<T> tree) {
        root = tree;
    }
    /**
     * Accessor for the left subtree
     * @return left subtree
     */
    public BinarySearchTree<T> left() {
        return new BinarySearchTree<T>(root.left);
    }
    /**
     * Accessor for the right subtree
     * @return right subtree
     */
    public BinarySearchTree<T> right() {
        return new BinarySearchTree<T>(root.right);
    }
    
    /**
     * Check for an empty tree
     * @returns true if tree is empty
     */
    public boolean isEmpty() {
        return root == null;
    }
    
    /**
     * Make the tree empty
     */
    public void makeEmpty() {
        root = null;
    }
    
    /**
     * Inserts an element into the tree
     * @param x - the new element
     * @return true if x was inserted
     */
    public boolean add(T x) {
        int oldSize = size;
        root = add(x,root);
        return oldSize != size;
    } // end add
    
    private BinaryTreeNode<T> add(T x, BinaryTreeNode<T> tree) {
        if( tree == null ) {
            tree = new BinaryTreeNode<T>(x);
            size++;
        } else if( compare(x,tree.data) < 0 ) {
            tree.left = add(x,tree.left);
        } else if( compare(x,tree.data) > 0 ) {
            tree.right = add(x,tree.right);
        } // end if
        return tree;
    } // end insert
    
    /**
     * Checks if an element is in the tree
     * @param x - the element to be checked
     * @returns true is x is in the tree
     */
    public boolean contains(Object x) {
        return contains((T)x,root);
    }
    
    private boolean contains(T x, BinaryTreeNode<T> t) {
        if( t == null ) return false;
        if( compare(x,t.data) < 0 ) {
            return contains(x,t.left);
        } else if( compare(x,t.data) > 0 ) {
            return contains(x,t.right);
        } else {
            return true;
        } // end if
    } // end contains
    
    
    /**
     * return a String representation of the nodes in the tree
     * @return a String representation of the nodes in inorder
     */
    public String toString() {
        return toString(root);
    }
    
    private String toString(BinaryTreeNode<T> tree) {
        String out = "";
        if( tree != null ) {
            out += toString(tree.left);
            out += tree.data.toString() + " ";
            out += toString(tree.right);
        } // end if
        return out;
    } // end toString
    
    /**
     * Return the first (minimum) value in the tree
     * @return the mimimum value in the tree
     */
    public T getMin() {
        return getMin(root);
    }
    
    private T getMin(BinaryTreeNode<T> tree)  {
        if( tree == null ) throw new NoSuchElementException();
        if( tree.left == null ) return tree.data;
        return getMin(tree.left);
    }
    
    /**
     * Remove the minimum value in the tree
     * @return the mimimum value in the tree
     */
    public T removeMin() {
        T save = getMin();
        root =  removeMin(root);
        return save;
    } // end removeMin
    
    private BinaryTreeNode<T> removeMin(BinaryTreeNode<T> tree)  {
        if( tree == null ) throw new NoSuchElementException();
        if( tree.left == null ) {
            size--;
            return tree.right;
        }
        tree.left = removeMin(tree.left);
        return tree;
    }
    
    /**
     * Removes an element from the tree
     * @param x - the element to be removed
     * @returns true of x is removed
     */
    public boolean remove(Object x)  {
        int oldSize = size;
        root = remove(x,root);
        return oldSize != size;
    }
    
    private BinaryTreeNode<T> remove(Object x, BinaryTreeNode<T> tree) {
        if( tree == null ) return null;
        if( compare((T)x,tree.data) < 0 ) {
            tree.left = remove(x,tree.left);
        } else if( compare((T)x,tree.data) > 0 ) {
            tree.right = remove(x,tree.right);
        } else if( tree.left != null && tree.right != null) {
            tree.data = getMin(tree.right);
            tree.right = removeMin(tree.right);
        } else {
            tree = (tree.left != null)?tree.left:tree.right;
            size--;
        }
        return tree;
    }
    
    /**
     * return an iterator for the tree
     * @return an inorder iterator for this tree
     */
    public Iterator<T> iterator() {
        return new InorderIterator<T>(root);
    } // end inorderIterator
    
    private class InorderIterator<T> implements Iterator<T> {
        BinaryTreeNode<T> current;
        Stack<BinaryTreeNode<T>> s;
        
        private InorderIterator(BinaryTreeNode<T> root) {
            current = root;
            s = new Stack<BinaryTreeNode<T>>();
            s.push(null);
            if( current != null ) goLeft();
        }
        
        private void goLeft() {
            while( current.left != null ) {
                s.push(current);
                current = current.left;
            } // end while
        } // end goLeft
        
        public boolean hasNext() {
            return current != null;
        } // end hasNext
        
        public T next() {
            if( !hasNext() ) throw new NoSuchElementException();
            BinaryTreeNode<T> save = current;
            if( current.right != null ) {
                current = current.right;
                goLeft();
            } else {
                current = s.pop();
            } // end if
            return save.data;
        } // end next
        
        public void remove() {
            throw new UnsupportedOperationException();
        }
        
    } // end InorderIterator
    
    private static class BinaryTreeNode<T> {
        T data;
        BinaryTreeNode<T> left;
        BinaryTreeNode<T> right;
        public BinaryTreeNode() {}
        public BinaryTreeNode(T item) {
            data = item;
            right = null;
            left = null;
        } // constructor
        public BinaryTreeNode(T item,BinaryTreeNode<T> left,BinaryTreeNode<T> right) {
            data = item;
            this.left = left;
            this.right = right;
        } // end constructor
        boolean isLeaf() {
            return left == null && right == null;
        }
        public String toString() {
            return data + "";
        } // end toString
    } // end BinaryTreeNode
    
    private int compare(T x, T y) {
        if( comparator == null ) {
            return ((Comparable<T>)x).compareTo(y);
        } else {
            return comparator.compare(x,y);
        } // end if
    } // end compare
    
} // end BinarySearchTree