import java.util.List;
import java.util.Optional;
import java.util.ArrayList;




 class BinaryTree implements BinaryTreeInterface {

     Node root;
public boolean add(int value){
    Node newNode = new Node(value);
    Node tmpnode=root;
    if (root ==null){
        root = newNode;
        return true;
}
    else
        while (true){
            if (root.getValue()==value)
                return false;
            if(tmpnode.nextLeft(value)){
                if (tmpnode.getValue()==value)
                    return false;
                if(tmpnode.isLeaf())
                    newNode.setLeft(tmpnode);
                    return true;
}
            else{
                if (tmpnode.getValue()==value)
                    return false;
                    if(tmpnode.isLeaf())
                        newNode.setRight(tmpnode);
                        return true;

}
}


}


public Node getRoot(){

    return root;
}

public Optional<List<Integer>> getPathTo(int value){
    List<Integer> list= new ArrayList<>();
    Optional<List<Integer>> op=Optional.ofNullable(list);
    list.add(root.getValue());
    Node tmpnode=root;

while(tmpnode.isLeaf()==false){
    if(tmpnode.getValue()==value)
        return op;
    if(tmpnode.nextLeft(value)){
        list.add(tmpnode.getValue());
        tmpnode.getLeft();
}
    else{
        list.add(tmpnode.getValue());
        tmpnode.getRight();
}

}

    return op;

}



  }


public class Node {
    private Node left;
    private Node right;
    private final int value;

    /**
     * Konstruktor klasy Node - odpowiada za ustawienie wartosci wezla.
     *
     * @param value
     *            wartosc wezla
     */
    public Node(int value) {
        this.value = value;
    }

    /**
     * Metoda zwraca wartosc zapisana w wezle.
     *
     * @return wartosc wezla
     */
    public int getValue() {
        return value;
    }

    /**
     * Metoda zwraca lewe poddrzewo lub null, jesli go nie ma.
     *
     * @return lewe poddrzewo lub null, jesli go nie ma
     */
    public Node getLeft() {
        return left;
    }

    /**
     * Metoda zwraca prawe poddrzewo lub null, jesli go nie ma.
     *
     * @return prawe poddrzewo lub null, jesli go nie ma.
     */
    public Node getRight() {
        return right;
    }

    /**
     * Metoda pozwala sprawdzic czy dany wezel jest lisciem, czyli nie ma zadnego
     * podlaczonego poddrzewa.
     *
     * @return true - wezel jest lisciem
     */
    public boolean isLeaf() {
        return (left == null) && (right == null);
    }

    /**
     * Metoda sprawdza czy poszukiwana wartosc value powinno szukac sie w lewym
     * poddrzewie. Metoda nie prawdzi poszukiwania.
     *
     * @param value
     *            poszukiwana wartsc
     * @return true - wartosci value nalezy szukac w lewym poddrzewie
     */
    public boolean nextLeft(int value) {
        if (value < this.value)
            return true;
        return false;
    }

    /**
     * Metoda sprawdza czy poszukiwana wartosc value powinno szukac sie w prawym
     * poddrzewie. Metoda nie prawdzi poszukiwania.
     *
     * @param value
     *            poszukiwana wartsc
     * @return true - wartosci value nalezy szukac w prawym poddrzewie
     */
    public boolean nextRight(int value) {
        if (value > this.value)
            return true;
        return false;
    }

    /**
     * Metoda dowiazuje lewy-wezel.
     *
     * @param node
     *            dolaczany wezel
     */
    public void setLeft(Node node) {
        left = node;
    }

    /**
     * Metoda dowiazuje prawy-wezel.
     *
     * @param node
     *            dolaczany wezel
     */
    public void setRight(Node node) {
        right = node;
    }
}