// TRAI_23_t16_18.java.java SJ


/**
 * 16. Kirjoita algoritmi joka etsii binääripuun vähiten syvän (lähimpänä juurta olevan) leh-
 * tisolmun. Vihje: tasoittainen läpikäynti. Aikavaativuus?
 *
 * 17. Kirjoita algoritmi, joka vertaa kahta binääripuuta ja palauttaa toden jos puut ovat raken-
 * teeltaan samat, muuten epätoden. Puut ovat rakenteeltaan samat, jos juuren molemmat
 * alipuut ovat keskenään rakenteeltaan samanlaiset. Puun sisältämiä alkioita ei siis vertailla,
 * vain puun rakennetta (”oksaston muotoa”). Aikavaativuus? Tilavaativuus? Vihje: rekursio
 * rinta rinnan molemmissa puissa.
 *
 * 18. Kirjoita algoritmi joka laskee annetun binääripuun eri solmujen suurimman lasten kor-
 * keuseron. Algoritmi siis selvittää mille binääripuun solmulle oikean ja vasemman alipuun
 * korkeusero on suurin ja palauttaa ko. korkeuseron. Algoritmia voisi käyttää AVL-puun
 * tasapainon tarkastamiseen, mutta muistetaan, ettei AVL-puun toteutus tarvise tälläis-
 * ta tarkastamista. Mikä on algoritmisi aikavaativuus? Aikavaativuus vaikuttaa hieman
 * tehtävän arvosteluun.
 */

import fi.uef.cs.tra.BTree;
import fi.uef.cs.tra.BTreeNode;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.concurrent.atomic.AtomicInteger;

public class TRAI_23_t16_18_pohja {

    public static void main(String[] args) {

        BTree<Integer> puu = null;


        // testataan ensin vakiopuulla

        puu = exampleBTree();
        System.out.println("Sisäjärjestyksessä:");
        inorderPrint(puu);

        System.out.println("Matalin lehtisolmu: " + matalinLehtisolmu(puu));

        int ero = suurinEro(puu);
        System.out.println("Suurin ero on " + ero);

        BTree<Integer> puu2 = exampleBTree();

        System.out.println("Samat rakenteet : " + vertaaRakenne(puu, puu2));

        System.out.println("\nLisätään: 8");
        inorderInsert(puu, 8);
        System.out.println("Samat rakenteet : " + vertaaRakenne(puu, puu2));

        System.out.println("Matalin lehtisolmu: " + matalinLehtisolmu(puu));

        ero = suurinEro(puu);
        System.out.println("Suurin ero on " + ero);

        System.out.println("\nLisätään: 3");
        inorderInsert(puu, 3);

        System.out.println("Matalin lehtisolmu: " + matalinLehtisolmu(puu));

        ero = suurinEro(puu);
        System.out.println("Suurin ero on " + ero);


        System.out.println();


    } // main()

    /**
     * Puun matalin lehtisolmu.
     * @param T syötepuu
     * @return matalin lehtisolmu
     * @param <E> puun solmujen alkioiden tyyppi
     */
    public static <E> BTreeNode<E> matalinLehtisolmu(BTree<E> T) {
        if (T.getRoot() == null)
            return null;

        // TODO

        return null;
    } // matalinLehtisolmu()


    /**
     * Puiden rakenteiden vertailu.
     * @param T1 syötepuu1
     * @param T2 syötepuu2
     * @param <E> alkiotyyppi (ei käytetä)
     * @return ovatko rakenteeltaan samat vai ei
     */
    public static <E> boolean vertaaRakenne(BTree<E> T1, BTree<E> T2) {
        // TODO
        return  false;
    } // vertaaRakenne()


    /**
     * Suurin puun solmujen tasapainoero. Siis solmujen lasten korkeusero.
     * @param T tarkasteltava binääripuu.
     * @return suurin korkeusaro puussa olevien solmujen lapsille
     **/
    public static <E> int suurinEro(BTree<E> T) {

        // TODO
        return 0;
    }



    // esimerkkejä ja pohjia


    public static BTree<Integer> exampleBTree() {

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

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

        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>(1));
        l.setRightChild(new BTreeNode<Integer>(7));

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

        // 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));
        l.getRightChild().setLeftChild(new BTreeNode<Integer>(17));


        System.out.println("                 ");
        System.out.println("       9        ");
        System.out.println("    __/  \\__     ");
        System.out.println("   5        15   ");
        System.out.println("  / \\      /  \\  ");
        System.out.println(" 1   7   12    18");
        System.out.println("  \\      /\\    / ");
        System.out.println("   2    11 13 17 ");
        System.out.println("                 ");

        return T;

    } // exampleBTree()



    /**
     * 15. Lisäys sisäjärjestettyyn binääripuuhun.
     * @param T binääripuu
     * @param x lisättävä alkio
     * @return tehtiinkö lisäys vai ei
     */
    public static <E extends Comparable<? super E>> boolean inorderInsert(BTree<E> T, E x) {
        BTreeNode<E> n = T.getRoot();
        if (n == null) {
            T.setRoot(new BTreeNode<E>(x));
            return true;
        }

        while (true) {

            if (x.compareTo(n.getElement()) == 0)
                // x on jo puussa, eli lisätä
                return false;

            else if (x.compareTo(n.getElement()) < 0) {
                // x edeltää n:n alkiota
                if (n.getLeftChild() == null) {
                    // lisäyskohta läydetty
                    n.setLeftChild(new BTreeNode<>(x));
                    return true;
                } else  // alas vasemmalle
                    n = n.getLeftChild();
            } else {
                // x suurempi kuin n
                if (n.getRightChild() == null) {
                    // lisäyskohta läydetty
                    n.setRightChild(new BTreeNode<>(x));
                    return true;
                } else  // alas oikealle
                    n = n.getRightChild();
            }
        } // while

    } // inorderInsert()


    // Tulostus sisäjärjestyksessä rekursiivisesti
    public static <E> void inorderPrint(BTree<E> T) {
        inorderPrintBranch(T.getRoot());
        System.out.println();
    } // inorderPrint()


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

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

    } // inorderPrintBranch()


} // class TRAI_23_t16_18.java