// Notkun: StringTreeNode t2 = insertIntoTree(t1,s);
// Fyrir:  t1 er tvíleitartré, má vera tómt.
// Eftir:  t2 er tvíleitartré sem inniheldur öll gildin
//         úr t1 og einnig hnút með strengnum s.
public static StringTreeNode insertIntoTree( StringTreeNode t, String s )
{
   if( t == null )
            t = new StringTreeNode(s, null, null);
    else if( s.compareTo( t.val ) < 0 )
            t.left = insertIntoTree( t.left, s);
    else if( s.compareTo( t.val ) > 0 )
            t.right = insertIntoTree( t.right, s );
    else if( s.compareTo( t.val) == 0 )
            t.right = insertIntoTree( t.right, s);
    return t;
}

// Notkun: String s = minInTree(t);
// Fyrir:  t er tvíleitartré, ekki tómt.
// Eftir:  s er minnsta gildið í t.
public static String minInTree( StringTreeNode t )
{
    if(t.left == null) return t.val;
    return minInTree(t.left);
}

// Notkun:  deleteMinInTree(t);
// Fyrir:   t er tvíleitartré, ekki tómt.
// Eftir:   búið er að eyða minnsta gildi úr tréinu t.
public static StringTreeNode deleteMinInTree( StringTreeNode t )
{
    if(t.left != null){

        t.left = deleteMinInTree(t.left);
        return t;
    }
    else return t.right;

}


// Notkun: StringTreeNode t2 = deleteFromTree(t1,s);
// Fyrir:  t1 er tvíleitartré, má vera tómt.
// Eftir:  t2 er tvíleitartré sem inniheldur öll gildin
//         úr t1 nema hvað búið er að fjarlægja einn hnút
//         með gildinu s ef einhver slíkur hnútur var til
//         staðar.
public static StringTreeNode deleteFromTree( StringTreeNode t, String s )
{
    if( t == null ) return null;
    if( s.compareTo( t.val ) < 0 )
        t.left = deleteFromTree( t.left, s );
    else if( s.compareTo( t.val ) > 0 )
        t.right = deleteFromTree( t.right, s);
    else if( t.left != null && t.right != null )
    {
        StringTreeNode x = new StringTreeNode(minInTree(t.right), t.left, t.right);
        t = x;
        t.right = deleteMinInTree( t.right );
    } else
        t = ( t.left != null ) ? t.left : t.right;
        return t;
}

// EKKI BREYTA HÉR FYRIR NEÐAN

private static int is( StringTreeNode t, int i, String[] a )
{
    if( t==null ) return i;
    if( t.left!=null ) i = is(t.left,i,a);
    if( !a[i].equals(t.val) ) throw new Error();
    return is(t.right,i+1,a);
}

private static boolean is( StringTreeNode t, String[] a )
{
    try
    {
        int i = is(t,0,a);
        return  i==a.length;
    }
    catch( Error e )
    {
        return false;
    }
}

public static String insertAndDelete()
{
    StringTreeNode t;
    String res = "Villa";
    t = null;
    t = insertIntoTree(t,"a");
    if( !is(t,new String[]{"a"}) ) return "A";
    t = insertIntoTree(t,"b");
    if( !is(t,new String[]{"a","b"}) ) return "B";
    t = insertIntoTree(t,"c");
    if( !is(t,new String[]{"a","b","c"}) ) return "C";
    t = insertIntoTree(t,"x");
    if( !is(t,new String[]{"a","b","c","x"}) ) return "X";
    t = insertIntoTree(t,"p");
    if( !is(t,new String[]{"a","b","c","p","x"}) ) return "P";
    t = insertIntoTree(t,"p");
    if( !is(t,new String[]{"a","b","c","p","p","x"}) ) return "P2";
    t = deleteFromTree(t,"a");
    if( !is(t,new String[]{"b","c","p","p","x"}) ) return "DA";
    t = deleteFromTree(t,"p");
    if( !is(t,new String[]{"b","c","p","x"}) ) return "DP";
    return "Engin villa";
}