/**
 * Write a description of class Oppgave1 here.
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public class Oppgave1
{
    private BinNode rot;

    /**
     * Constructor for objects of class Oppgave1
     */
    public Oppgave1()
    {
        rot = null;
        lagTre();
        System.out.println("Mitt forslag:");
        intervall(rot, 0, 5);
        System.out.println("\nL?sningsforslag");
        skrivIntervall(rot, 0, 5);
    }

    /**
     * Opprett treet.
     */
    public void lagTre()
    {
        insert(10);
        insert(6);
        insert(5);
        insert(4);
        insert(3);
        insert(0);
        insert(0);
        insert(4);
        insert(0);
        insert(8);
    }
    
    /**
     * Sett inn en node i treet.
     */
    private void insert(int tall)
    {
        BinNode ny = new BinNode(tall);
        if(rot == null)
        {
            rot = ny;
        }
        else
        {
            BinNode denne = rot;
            while(true)
            {
                if(tall <= denne.data)
                {
                    if(denne.vsub == null)
                    {
                        denne.vsub = ny;
                        break;
                    }
                    else
                    {
                        denne = denne.vsub;
                    }
                }
                else
                {
                    if(denne.hsub == null)
                    {
                        denne.hsub = ny;
                        break;
                    }
                    else
                    {
                        denne = denne.hsub;
                    }
                }
            }
        }
    }
    
    /**
     * Print ut tall mellom et gitt intervall min og max, og hvor hvert tall
     * bare skal printes ut ?n gang. Rekursiv.
     */
    private void intervall(BinNode t, int min, int max)
    {
        if(max < min) return;
        
        //sjekk venstre subtre
        if(t.vsub != null && (t.vsub.data >= min && t.vsub.data > max))
        {
            intervall(t.vsub, min, max);
            min = t.vsub.data+1;
        }
        else if(t.vsub != null && t.vsub.data >= min)
        {
            intervall(t.vsub, min, t.data);
            min = t.vsub.data+1;
        }
        else if(t.vsub == null)
        {
            min = t.data;
        }
        
        //sjekk om denne noden skal skrives ut
        if(t.data >= min && t.data <= max)
        {
            System.out.println(t.data);
        }
        
        //sjekk h?yre og pass p? like verdier, t.data er den nye min
        if(t.hsub != null && (t.hsub.data < max && t.hsub.data > min))
        {
            intervall(t.hsub, min, max);
        }
    }
    
    /**
     * L?sningsforslaget...
     */
    void skrivIntervall( BinNode t, int min, int max ) {
        if( t == null || max < min ) return;
        int d = t.data;
        if( d > min ) skrivIntervall( t.vsub, min, max );
        if( d >= min && d <= max ) System.out.println( t.data );
        if( d < max ) skrivIntervall( t.hsub, min, max );
    }
            
}