import java.util.Comparator;
import java.util.Random;

class BST<AnyType>
{
    public BST( )
    {
        this( null );
    }

    public BST( Comparator<? super AnyType> c )
    {
        root = null;
        theSize = 0;
        cmp = c;
    }


    public boolean isEmpty( )
    {
        return size( ) == 0;
    }

    public void clear( )
    {
        theSize = 0;
        root = null;
    }

    public int getSize( )
    {
        return size( root );
    }

    public int countTwoChars( )
    {
        return countTwoChars( root );
    }

    private int countTwoChars( Node<AnyType> t )
    {
        if( t == null )
            return 0;

        int count = 0;
        if( t.data.toString( ).length( ) == 2 )
            count++;

        return countTwoChars( t.left ) + countTwoChars( t.right ) + count;


    }


    private int size( Node<AnyType> t )
    {
        if( t == null )
            return 0;
        else
            return size( t.left ) + size( t.right ) + 1;
    }

    public int size( )
    {
        return theSize;
    }

    // Public driver
    public boolean contains( AnyType x )
    {
        return contains( root, x );
    }

    // Private recursive routine
    private boolean contains( Node<AnyType> t, AnyType x )
    {
        if( t == null )
            return false;

        int result = myCompare( x, t.data );
        if( result == 0 )
            return true;
        else if( result < 0 )
            return contains( t.left, x );
        else
            return contains( t.right, x );
    }

    // Driver
    public boolean add( AnyType x )
    {
        int oldSize = size( );
        root = add( root, x );
        return size( ) != oldSize;
    }

    // Recursive
    // Add x to subtree t; return the resulting subtree
    private Node<AnyType> add( Node<AnyType> t, AnyType x )
    {
        if( t == null )
        {
            theSize++;
            return new Node( x, null, null );
        }

        int result = myCompare( x, t.data );
        if( result < 0 )
            t.left = add( t.left, x );
        else if( result > 0 )
            t.right = add( t.right, x );

        return t;
    }

    public boolean remove( AnyType x )
    {
        int oldSize = size( );
        root = remove( root, x );
        return size( ) != oldSize;
    }

    private Node<AnyType> remove( Node<AnyType> t, AnyType x )
    {
        if( t == null )
            return t;

        int result = myCompare( x, t.data );
        if( result < 0 )
            t.left = remove( t.left, x );
        else if( result > 0 )
            t.right = remove( t.right, x );
        else
        {
            // THIS IS THE NODE TO REMOVE!
            if( t.left != null && t.right != null )
            {
                t.data = findMin( t.right );
                t.right = removeMin( t.right );
            }
            else
            {  // ZERO OR ONE CHILD
                if( t.left == null )  // Covers zero child case
                    t = t.right;
                else if( t.right == null )
                    t = t.left;

                theSize--;
            }
        }

        return t;
    }

    // t != null
    private Node<AnyType> removeMin( Node<AnyType> t )
    {
        if( t.left == null )
        {
            theSize--;
            return t.right;
        }

        t.left = removeMin( t.left );
        return t;
    }


    // t != null
    private AnyType findMin( Node<AnyType> t )
    {
        if( t.left == null )
            return t.data;
        else
            return findMin( t.left );
    }

    // t != null
    private AnyType findMax( Node<AnyType> t )
    {
        Node<AnyType> p = t;
        while( p.right != null )
            p = p.right;

        return p.data;
    }

    public String toString( )
    {
        StringBuilder sb = new StringBuilder( );

        sb.append( "[" );
        toString( root, sb );
        sb.append( " ]" );

        return new String( sb );
    }

    private void toString( Node<AnyType> t, StringBuilder sb )
    {
        if( t != null )
        {
            toString( t.left, sb );
            sb.append( " " + t.data );
            toString( t.right, sb );
        }
    }


    public int height( )
    {
        return height( root );
    }

    private int height( Node<AnyType> t )
    {
        if( t == null )
            return -1;
        else
            return 1 + Math.max( height( t.left ), height( t.right ) );
    }
    
    private static class Node<AnyType>
    {
        Node( AnyType d, Node<AnyType> lft, Node<AnyType> rgt )
        {
            data = d;
            left = lft;
            right = rgt;
        }

        AnyType data;
        Node<AnyType> left;
        Node<AnyType> right;
    }

    private int myCompare( AnyType lhs, AnyType rhs )
    {
        if( cmp != null )
            return cmp.compare( lhs, rhs );
        else
            return ((Comparable)lhs).compareTo( rhs );
    }

    private Node<AnyType> root;
    private int theSize;
    private Comparator<? super AnyType> cmp;
}

class Day13
{
    public static void main( String [ ] args )
    {
        BST<Integer> bst = new BST<Integer>( );
        Random r = new Random( );
        final int M = 1000;
        final int N = M * M;

        while( true )
        {
            bst.clear( );
            for( int i = 0; i < N; i++ )
                bst.add( r.nextInt( M ) );

            if( bst.size( ) == M )
                break;
        }

        System.out.println( bst.getSize( ) );
        System.out.println( bst.countTwoChars( ) );
        System.out.println( bst.height( ) );

        for( int i = 0; i < M; i += 2 )
            bst.remove( i );

        for( int i = 0; i < M; i += 2 )
            if( bst.contains( i ) )
                System.out.println( "OOPS! " + i );


        for( int i = 1; i < M; i += 2 )
            if( !bst.contains( i ) )
                System.out.println( "OOPS! " + i );

        System.out.println( bst );
        System.out.println( bst.getSize( ) );
        System.out.println( bst.countTwoChars( ) );
        System.out.println( bst.height( ) );
    }
}