// tra1_2010_x3_pohja.java SJ

import fi.joensuu.cs.tra.*;
import java.util.Random;

public class tra1_2010_x3_pohja {

	public static void main(String[] args) {

        // luodaan puu
		BTree<Integer> puu = exampleBTree();
		
        // tulostetaan sisäjärjestyksessä
		System.out.println("Sisajarjestyksessa:");
		inorderPrint(puu);

        // tulostetaan takaperin testaten
        // X3-tehtävää
        System.out.println("Takaperin:");
        BTreeNode<Integer> n = inorderLast(puu);
        while (n != null) {
            System.out.print(n.getElement() + " ");
            n = inorderPrevious(n);
        }
        System.out.println();
		
	} // main()


	/* Luo pienen sisajarjestyn esimerkkipuun
	                 
	       10        
	    __/  \__     
	   5        15   
	  / \      /  \  
	 3   8   12    18
	  \      /\      
	   4    11 13    
	                 
	*/
	public static BTree<Integer> exampleBTree() {

		BTree<Integer> T = new BTree<Integer>();

		// juuri
		T.setRoot(new BTreeNode<Integer>(10));

		BTreeNode<Integer> n = T.getRoot();

		// juuren lapset
		n.setLeftChild(new BTreeNode<Integer>(5));
		n.setRightChild(new BTreeNode<Integer>(15));

		// vasen haara
		BTreeNode<Integer> l = n.getLeftChild();

		l.setLeftChild(new BTreeNode<Integer>(3));
		l.setRightChild(new BTreeNode<Integer>(8));

		l.getLeftChild().setRightChild(new BTreeNode<Integer>(4));

		// oikea haara
		l = n.getRightChild();

		l.setLeftChild(new BTreeNode<Integer>(12));
		l.setRightChild(new BTreeNode<Integer>(18));

		l.getLeftChild().setLeftChild(new BTreeNode<Integer>(11));
		l.getLeftChild().setRightChild(new BTreeNode<Integer>(13));


		System.out.println("                 ");
		System.out.println("       10        ");
		System.out.println("    __/  \\__     ");
		System.out.println("   5        15   ");
		System.out.println("  / \\      /  \\  ");
		System.out.println(" 3   8   12    18");
		System.out.println("  \\      /\\      ");
		System.out.println("   4    11 13    ");
		System.out.println("                 ");

		return T;

	} // exampleBTree()



    /**
      * Palauttaa binääripuun oikeanpuoleisimman solmun (sisäjärjestyksessä
      * viimeisen solmun).
      * @param T binääripuu
      * @return T:n oikeanpuoleisin solmu.
      */
    public static BTreeNode inorderLast(BTree T) {

        // X3a

        return null;
    }

    /**
      * Palauttaa annetun solmun edeltäjäsolmun sisäjärjestyksessä.
      * @param n solmu jonka edeltäjää haetaan
      * @return n:n edeltäjäsolmu, tai null jollei edeltäjää ole
      */
    public static BTreeNode inorderPrevious(BTreeNode n) {

        // X3b

        return null;

    }   // inorderPrevious()



	// Tulostus sisajarjestyksessa rekursiivisesti
	public static void inorderPrint(BTree T) {
		inorderPrintBranch(T.getRoot());
		System.out.println();
	} // inorderPrint()


	public static void inorderPrintBranch(BTreeNode n) {
		if (n == null)
			return;

		inorderPrintBranch(n.getLeftChild());
		System.out.print(n.getElement() + " ");
		inorderPrintBranch(n.getRightChild());

	} // inorderPrintBranch()

	
} // class tra1_2010_x3_pohja