Stablo Baki

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

class StabloOsoba {

    // Tip koji opisuje jedan cvor u stablu
    protected static class Cvor {

        // Sadrzaj cvora
        public Osoba osoba;

        // Levo i desno podstablo
        public Cvor levo;
        public Cvor desno;

        // Jedini konstruktor
        public Cvor(Osoba osoba, Cvor levo, Cvor desno) {
            this.osoba = osoba;
            this.levo = levo;
            this.desno = desno;
        }
    }

    // Stablo ima referencu na korenski cvor
    protected final Cvor koren;

    // Kreiramo prazno stablo
    public StabloOsoba() {
        koren = null;
    }

    // Kreiramo stablo sa jednom osobom u korenu
    // i praznim levim i desnim podstablom
    public StabloOsoba(Osoba osoba) {
        koren = new Cvor(osoba, null, null);
    }

    // Specijalan konstruktor koji koriste neki metodi ove klase
    protected StabloOsoba(Cvor koren) {
        this.koren = koren;
    }

    public boolean jePrazno() {
        return this.koren == null;
    }

    public boolean postojiElement(Cvor cvor, Osoba element) {
        if(cvor == null)
            return false;
        if(cvor.osoba.equals(element))
            return true;

        boolean nadjenLevo = postojiElement(cvor.levo, element);
        if (nadjenLevo) {
            return nadjenLevo;
        }

        boolean nadjenDesno = postojiElement(cvor.desno, element);
        if (nadjenDesno) {
            return nadjenDesno;
        }

        return false;
    }

    public void stampajPreorder(Cvor cvor) {
        if(cvor == null)
            return;
        System.out.println(cvor.osoba);
        stampajPreorder(cvor.levo);
        stampajPreorder(cvor.desno);

    }

    public void stampajInOrder(Cvor cvor){
        if(cvor == null)
            return;

        stampajInOrder(cvor.levo);
        System.out.println(cvor.osoba);
        stampajInOrder(cvor.desno);

    }

    public void stampajPostOrder(Cvor cvor){
        if(cvor == null)
            return;

        stampajPostOrder(cvor.levo);
        stampajPostOrder(cvor.desno);
        System.out.println(cvor.osoba);

    }

    public void stampajListove(Cvor cvor) {
        if(cvor == null)
            return;
        if(cvor.levo == null && cvor.desno == null)
            System.out.println(cvor.osoba);

        stampajListove(cvor.levo);
        stampajListove(cvor.desno);

    }

    private StabloOsoba pronadji(Osoba element) {
        if(element == null)
            return null;
        else
            return pronadji(this.koren, element);
    }

    private StabloOsoba pronadji(Cvor cvor, Osoba element) {
        if(cvor == null)
            return null;
        if(cvor.osoba.equals(element))
            return new StabloOsoba(cvor);

        StabloOsoba stabloLevo = pronadji(cvor.levo, element);
        if (stabloLevo != null) {
            return stabloLevo;
        }

        StabloOsoba stabloDesno = pronadji(cvor.desno, element);
        if (stabloDesno != null) {
            return stabloDesno;
        }

        return null;
    }

    public List<Osoba> stampajSveIspod(Osoba element){
        if(element == null)
            return null;

        StabloOsoba korenElementa = pronadji(element);

        return stampajSveIspod(new ArrayList<Osoba>(), korenElementa.koren);

    }

    private List<Osoba> stampajSveIspod(List<Osoba> lista, Cvor cvor){
        if(cvor == null)
            return null;

        lista.add(cvor.osoba);

        stampajSveIspod(lista ,cvor.levo);
        stampajSveIspod(lista ,cvor.desno);

        return lista;
    }

    public boolean ubaci(Osoba roditelj, Osoba potomak, boolean levo) {
        if(roditelj == null || potomak == null)
            return false;
        StabloOsoba stablo = pronadji(roditelj);
        Cvor cvor = stablo == null ? null : stablo.koren;

        if(cvor == null)
            return false;

        if(cvor.desno != null || cvor.levo != null)
            return false;
        return ubaci(this.koren,roditelj, potomak, levo);
    }

    private boolean ubaci(Cvor cvor, Osoba roditelj, Osoba potomak, boolean levo) {
        if(cvor == null)
            return false;

        if(roditelj.equals(cvor.osoba))
            return true;

        //Verovatno sam ga zakomplikovao, ali barem radi <3
        boolean nadjenLevo = ubaci(cvor.levo, roditelj, potomak, levo);
        if (nadjenLevo) {
            if(levo)
                cvor.levo.levo = new Cvor(potomak, null, null);
            else
                cvor.levo.desno = new Cvor(potomak, null, null);
            return nadjenLevo;
        }

        boolean nadjenDesno = ubaci(cvor.desno, roditelj, potomak, levo);
        if (nadjenDesno) {
            if(levo)
                cvor.desno.levo = new Cvor(potomak, null, null);
            else
                cvor.desno.desno = new Cvor(potomak, null, null);
            return nadjenDesno;
        }

        return false;
    }

    public Osoba roditeljOd(Osoba potomak) {
        if(this.koren.osoba.equals(potomak) || koren == null)
            return null;
        return roditeljOd(this.koren, potomak);
    }

    private Osoba roditeljOd(Cvor cvor, Osoba potomak) {
        if(cvor == null)
            return null;
        /*
        Prvo proveravamo da li postoji osoba na levoj ili desnoj grani.
        Ovo radimo da nam ne bi izbacio null-point-exception u slucajevima kada
        postoji ili samo leva ili samo desna osoba.
        Ovo radimo preko "lenjog izracunavanja", ako vidi da nema osobe na nekoj strani
        on nece ni proveravati da li je na toj strani potomak!
         */
        if((cvor.levo != null && cvor.levo.osoba.equals(potomak))||
                (cvor.desno != null && cvor.desno.osoba.equals(potomak)))
            return cvor.osoba;

        Osoba leva = roditeljOd(cvor.levo, potomak);
        if(leva != null)
            return leva;

        Osoba desna = roditeljOd(cvor.desno, potomak);
        if(desna != null)
            return desna;

        return null;
    }

    public Osoba optimalnaOsoba(Comparator<Osoba> komparator, Cvor cvor) {
        return null;
    }

}