import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.TreeSet;
import sun.misc.Queue;

/**
 * Binary Search Tree that inherits from the TreeSet class
 * The class is based on Weiss's non-generic implementation of BinarySearchTree
 *
 * @author Daniel
 * @param <T>
 */
public class BinarySearchTree<T extends Comparable<T>> extends TreeSet<T> implements Iterable<T>
{
    /**
     * Construct the tree.
     */
    public BinarySearchTree( )
    {
        root = null;
    }

    @Override
    public boolean add(T e)
    {
        insert(e);
        return true;
    }



    /**
     * Insert into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert( Comparable x )
    {
        {

            root = insert( x, root );

        }

    }

    /**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove( Comparable<T> x )
    {

        root = remove( x, root );


    }

    /**
     * Find the smallest item in the tree.
     * @return smallest item or null if empty.
     */
    public Comparable findMin( )
    {
        return elementAt( findMin( root ) );
    }

    /**
     * Find the largest item in the tree.
     * @return the largest item of null if empty.
     */
    public Comparable findMax( )
    {
        return elementAt( findMax( root ) );
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    public Comparable find( Comparable x )
    {
        return elementAt( find( x, root ) );
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( )
    {
        root = null;
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    /**
     * Internal method to get element field.
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private Comparable elementAt( BinaryNode t )
    {
        return t == null ? null : t.element;
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private BinaryNode insert( Comparable<T> x, BinaryNode<T> t )
    {
/* 1*/      if( t == null )
            {
/* 2*/          t = new BinaryNode( x, null, null );

                t.parent = null;
                if (t.left != null)
                    t.left.parent = t;
                if (t.right != null)
                    t.right.parent = t;
            }
/* 3*/      else if( x.compareTo((T)t.element ) < 0 )
            {
/* 4*/          t.left = insert( x, t.left );
                t.left_count++;
                t.left.parent = t;

            }
/* 5*/      else if( x.compareTo((T) t.element ) > 0 )
            {
/* 6*/          t.right = insert( x, t.right );
                t.right.parent = t;

            }
/* 7*/      else
/* 8*/          ;  // Duplicate; do nothing
/* 9*/      return t;
    }

    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private BinaryNode remove( Comparable<T> x, BinaryNode<T> t )
    {
        if( t == null )
            return t;   // Item not found; do nothing
        if( x.compareTo( (T)t.element ) < 0 )
        {
            t.left = remove( x, t.left );

        }
        else if( x.compareTo( (T)t.element ) > 0 )
        {
            t.right = remove( x, t.right );


        }
        else if( t.left != null && t.right != null ) // Two children
        {
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );


        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        if (t != null)
        {
            if (t.left != null)
                t.left.parent = t;
            if (t.right != null)
                t.right.parent = t;
        }
        return t;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    private BinaryNode<T> findMin( BinaryNode<T> t )
    {
        if( t == null )
            return null;
        else if( t.left == null )
            return t;
        return findMin( t.left );
    }

    /**
     * Internal method to find the largest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private BinaryNode<T> findMax( BinaryNode<T> t )
    {
        if( t != null )
            while( t.right != null )
                t = t.right;

        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private BinaryNode find( Comparable<T> x, BinaryNode<T> t )
    {
        if( t == null )
            return null;
        if( x.compareTo( (T)t.element ) < 0 )
            return find( x, t.left );
        else if( x.compareTo( (T)t.element ) > 0 )
            return find( x, t.right );
        else
            return t;    // Match
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the tree.
     */
    private void printTree( BinaryNode<T> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }


  @Deprecated
 //Updates nodes current parent
 // Unfortunaetly to expensive as it is O(N) algorithm.
 // Therefore it sadly didn't make the final cut and is a deprecated method can be removed in the near future.
 private void update(BinaryNode<T> t)
 {
     if (t != null)
     {
         if (t.left != null)
            t.left.parent = t;
         if (t.right != null)
            t.right.parent = t;
         update(t.left);
         update(t.right);
     }
 }


 /**
 * Returns an iterator pointing just before the
 * item in the tree with the lowest value.
 *
 **/

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


 /**
 * Returns the element at a given index position.
 * Throws an IndexOutOfBoundsException if the item is not found.
 * Runs in average O(log N) time.
 */
 public T get( int index )
 {
      return get(root, index);
 }

 private T get(BinaryNode<T> root, int index)
 {
     if (root == null) return null;
     if (root.left_count == index-1) return (T)root.element;
     if (root.left_count < index) return get(root.right, index - (root.left_count + 1));
     else
     {
         return get(root.left, index);
     }
 }


 /**
 * Returns all elements falling within a range of indexes.
 * The range is inclusive
 */

 public Collection<T> getRange( int first, int last )
 {
     ArrayList<T> list = new ArrayList<>();
     for(int i = first; i <= last; i++)
     {
         list.add(get(i));
     }
     return list;
 }

 /**
 * Prints the tree in level-order, which means the root is printed,
 * then all nodes at level 2, then nodes at level 3, and so on.
 */
 public void printLevelOrder( ) throws InterruptedException
 {
     Queue Q = new Queue();
     Q.enqueue(root);
     while(!Q.isEmpty())
     {
        BinaryNode<T> node =  (BinaryNode<T>)Q.dequeue();
        System.out.print(node.element + ",");
        if (node.left != null)
            Q.enqueue(node.left);
        if (node.right != null)
            Q.enqueue(node.right);
     }
     System.out.println();
 }






 private class MyIterator implements Iterator<T>
 {

        private BinaryNode<T> nextNode = null;
        private boolean firstCall;
        public MyIterator()
        {
            nextNode = BinarySearchTree.this.findMin(root);
            firstCall = true;
        }
        @Override
        public boolean hasNext()
        {
            return !nextNode.equals(BinarySearchTree.this.findMax(root));
        }

        @Override
        public T next()
        {
            if (firstCall)
            {
                firstCall = false;
                return (T)nextNode.element;
            }
            if (!hasNext())
                   throw new IndexOutOfBoundsException("Cannot manke another next() call!!!!?!");
            BinaryNode<T> node = successor(nextNode);
            nextNode = node;
            return (T)node.element;
        }

        @Override
        public void remove()
        {
            BinarySearchTree.this.remove(nextNode.element);
        }

        /**
        * Returns the next value in the sequence, starting at the
        * node pointed to by the input parameter. This method
        * is used by the iterator.
        */
        private BinaryNode<T> successor( BinaryNode<T> p )
        {
              BinaryNode<T> n = p.right;
              if (n != null)
              {
                  return BinarySearchTree.this.findMin(n);
              }
              else
              {
                 n = p.parent;
                 while(n != null && p == n.right)
                 {
                     p = n;
                     n = n.parent;
                 }
                 return n;
              }
        }


 }



      /** The tree root. */
    private BinaryNode<T> root;



    public static void main(String[] arguments) throws InterruptedException
    {

        BinarySearchTree<String> t = new BinarySearchTree<>();
        String[] array = { "Harry","Maria","Bob","Dan","Sue","Ann","Jose" };

        for(int i = 0; i < array.length; i++)
                t.insert(array[i]);
        print( t );

        System.out.print("Level order: ");
        t.printLevelOrder();
        System.out.println("n");

        System.out.printf( "The value at index %d is %sn", 0, t.get(0) );
        System.out.printf( "The value at index %d is %sn", 2, t.get(2) );
        System.out.printf( "The value at index %d is %sn", 6, t.get(6) );

        System.out.print("nRemoving ");
        for( int i = 1; i < array.length; i+= 2 ) {
                System.out.print(array[i] + ", ");
                t.remove( array[i] );
        }
        System.out.println();

        System.out.println("nTree contents after removing elements:");
        print( t );

        // verify that the get method still works
        System.out.printf( "The value at index %d is %sn", 0, t.get(0) );
        System.out.printf( "The value at index %d is %sn", 2, t.get(2) );
        System.out.printf( "The value at index %d is %sn", 3, t.get(3) );


    }

    public static void print( BinarySearchTree<? extends Comparable<?>> t )
    {

        for(Object x : t)
        System.out.print(x + ", ");
        System.out.println("n");
    }

 private static void test1() throws InterruptedException
 {
        BinarySearchTree<Integer> t = new BinarySearchTree<>( );
        int[] array = { 20, 10, 11, 30, 2, 29, 33, 28, 17, 4 };
         for(int i = 0; i < array.length; i++)
             t.add(array[i]);

        print( t ); // demonstrate the iterator

        System.out.println("Level order");
        t.printLevelOrder();

        System.out.printf( "The value at index %d is %dn", 0, t.get(0) );
        System.out.printf( "The value at index %d is %dn", 1, t.get(1) );
        System.out.printf( "The value at index %d is %dn", 2, t.get(2) );
        System.out.printf( "The value at index %d is %dn", 3, t.get(3) );
        System.out.printf( "The value at index %d is %dn", 8, t.get(8) );
        System.out.printf( "The value at index %d is %dn", 9, t.get(9) );

        System.out.print("nRemoving ");
        for( int i = 1; i < array.length; i+= 2 ) {
        System.out.print(array[i] + ", ");
        t.remove( array[i] );
        }
        System.out.println();

        System.out.println("nTree contents after removing elements:");
        print( t );

        // verify that the get method still works
        System.out.printf( "The value at index %d is %dn", 0, t.get(0) );
        System.out.printf( "The value at index %d is %dn", 1, t.get(1) );
        System.out.printf( "The value at index %d is %dn", 2, t.get(2) );
        System.out.printf( "The value at index %d is %dn", 3, t.get(3) );
        }




}

/**
 * Returns the element at a given index position.
 * Throws an IndexOutOfBoundsException if the item is not found.
 * Runs in average O(log N) time.
 */
 public T get( int index )
 {
      return get(root, index);
 }

 private T get(BinaryNode<T> root, int index)
 {
     if (root == null) return null;
     if (root.left_count == index-1) return (T)root.element;
     if (root.left_count < index) return get(root.right, index - (root.left_count + 1));
     else
     {
         return get(root.left, index);
     }
 }

Ann, Bob, Dan, Harry, Jose, Maria, Sue,

Level order: Harry,Bob,Maria,Ann,Dan,Jose,Sue,


The value at index 0 is Ann
The value at index 2 is Dan
The value at index 6 is Sue

Removing Maria, Dan, Ann,

Tree contents after removing elements:
Bob, Harry, Jose, Sue,

The value at index 0 is null
The value at index 2 is null
The value at index 3 is Harry

if (root.left_count == index-1) return (T)root.element;

if (root.left_count == index) return (T)root.element;