import java.util.*; // nur fuer meine Iteratoren benoetigt
/**
 * AlgoDat SS00, Aufgaben 52,53,54,55
 * Binaerer Suchbaum
 * 
 * @author Christian Semrau
 * <a href="mailto:gsemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */
class LinkedBinaryTree {
    // Wurzel des Baumes
    // protected, damit erbende Klassen darauf zugreifen koennen
    protected TreeNode root = null;
    // root wird waehrend der Konstruktion des Objekts auf null gesetzt

// deshalb hat der Konstruktor nix zu tun
public LinkedBinaryTree() {
}

/** Fuegt das Objekt sortiert in den Baum ein.
 * Liefert true, wenn obj eingefuegt wurde, false sonst.
 */
public boolean insert(Comparable x) {
    if (root==null){  // Baum ist noch leer
        root = new TreeNode(x);
        return true;
    }

    // rekursive Version
//    return root.insert(x);

    // iterative Version
    TreeNode B = root;
    while (true){  // Endlosschleife, wird von innen durch return beendet
        if (x.compareTo(B.getElement())==0){  // (x==B.element)
            return false;
        }
        if (x.compareTo(B.getElement())<0){  // (x<B.element)
            if (B.getLeft() == null){  // kein linker Unterbaum vorhanden
                B.setLeft(new TreeNode(x));
                return true;
            }else
                B = B.getLeft();  // wir muessen im linken Unterbaum einfuegen
        }else{  // (x>B.element)
            if (B.getRight() == null){
                B.setRight(new TreeNode(x));
                return true;
            }else
                B = B.getRight();
        }
    }
} // insert


    // ------------------------------
    // -- DURCHLAUFUNGEN DES BAUMS --
    // ------- Aufgaben 53,54 -------
    // ------------------------------

/** Liefert einen String, der den Inhalt des Baumes in Preorder enthaelt. */
public String traversePreorder() {
    return traversePreorder(root);
}
private String traversePreorder(TreeNode B) {
    if (B==null) return "";
    else return
        B+" "+
        traversePreorder(B.getLeft())+
        traversePreorder(B.getRight());
}

/** Liefert einen String, der den Inhalt des Baumes in Inorder enthaelt. */
public String traverseInorder() {
    return traverseInorder(root);
}
private String traverseInorder(TreeNode B) {
    if (B==null) return "";
    else return
        traverseInorder(B.getLeft())+
        B+" "+
        traverseInorder(B.getRight());
}

/** Liefert einen String, der den Inhalt des Baumes in Postorder enthaelt. */
public String traversePostorder() {
    return traversePostorder(root);
}
private String traversePostorder(TreeNode B) {
    if (B==null) return "";
    else return
        traversePostorder(B.getLeft())+
        traversePostorder(B.getRight())+
        B+" ";
}

/** Liefert einen String, der den Inhalt des Baumes in Levelorder enthaelt. */
public String traverseLevelorder() {
    if (root==null) return "";
    String s = "";
    ListDeque q = new ListDeque();
    q.insertFirst(root);
    while (!q.empty()){
        TreeNode e = (TreeNode)q.removeLast();
        if (e.getLeft()!=null) q.insertFirst(e.getLeft());
        if (e.getRight()!=null) q.insertFirst(e.getRight());
        s += e+" ";
    }
    return s;
}


    // --------------------------------
    // -- WEITERE METHODEN DES BAUMS --
    // --------- Aufgabe 55 -----------
    // --------------------------------

/** Liefert die Hoehe des Baumes. */
public int getHeight() {
    return root==null ? 0 : root.getHeight();
}

/** Liefert die Anzahl der Knoten im Baum. */
public int getNrOfNodes() {
    return root==null ? 0 : root.getNrOfNodes();
}

/** true, wenn die Wurzel balanciert ist. */
public boolean isBalanced() {
    return root==null ? true : root.isBalanced();
}

/** true, wenn jeder einzelne Knoten des Baumes balanciert ist. */
public boolean isCompleteBalanced() {
    return root==null ? true : root.isCompleteBalanced();
}

    // ---------------------------
    // -- ITERATOREN DES BAUMS ---
    // -- waren nicht gefordert --
    // ---------------------------

/** Liefert einen Iterator, der den Baum per Inorder durchlaeuft. */
public Iterator iteratorInorder() {
    return new InorderIterator();
}
/** Liefert einen Iterator, der den Baum per Levelorder durchlaeuft. */
public Iterator iteratorLevelorder() {
    return new LevelorderIterator();
}
/** Liefert einen Iterator, der den Baum per Postorder durchlaeuft. */
public Iterator iteratorPostorder() {
    return new PostorderIterator();
}
/** Liefert einen Iterator, der den Baum per Preorder durchlaeuft. */
public Iterator iteratorPreorder() {
    return new PreorderIterator();
}

    // Oberklasse aller Iteratoren des Baumes
    abstract class TreeIterator implements Iterator{
        // q wird von LevelorderIterator als Queue, von den anderen
        // als Stack genutzt
        protected ListDeque q = new ListDeque();
        public boolean hasNext(){
            return !q.empty();
        }
        // public Object next() wird von der erbenden Klasse implementiert
        public void remove(){
            // Loeschen geht nicht, koennte aber realisiert werden.
            // Dann muessten alle Iteratoren den kompletten Baum
            // in die Deque laden, denn beim Loeschen veraendert sich
            // die Reihenfolge der Knoten, der Iterator soll aber die
            // anfaengliche Reihenfolge beibehalten.
            throw new UnsupportedOperationException();
        }
    };

    // Durchlaeuft den Baum in Preorder
    // speichert hoechstens 2*root.getHeight() Knoten in der Deque
    class PreorderIterator extends TreeIterator{
        public PreorderIterator(){
            if (root!=null) q.insertFirst(root);
        }
        public Object next(){
            if (!hasNext())
                throw new NoSuchElementException();
            TreeNode current = (TreeNode)q.removeFirst();
            Object el = current.getElement();
            if (current.getRight()!=null)
                q.insertFirst(current.getRight());
            if (current.getLeft()!=null)
                q.insertFirst(current.getLeft());
            return el;
        }
    };

    // Durchlaeuft den Baum in Inorder
    // speichert alle Knoten in der Deque
    class InorderIterator extends TreeIterator{
        public InorderIterator(){
            if (root!=null) push(root);
        }
        public Object next(){
            if (!hasNext())
                throw new NoSuchElementException();
            TreeNode current = (TreeNode)q.removeFirst();
            Object el = current.getElement();
            return el;
        }
        private void push(TreeNode B){
            if (B!=null){
                push(B.getRight());
                q.insertFirst(B);
                push(B.getLeft());
            }
        }
    };

    // Durchlaeuft den Baum in Postorder
    // speichert alle Knoten in der Deque
    class PostorderIterator extends TreeIterator{
        public PostorderIterator(){
            if (root!=null) push(root);
        }
        public Object next(){
            if (!hasNext())
                throw new NoSuchElementException();
            TreeNode current = (TreeNode)q.removeFirst();
            Object el = current.getElement();
            return el;
        }
        private void push(TreeNode B){
            if (B!=null){
                q.insertFirst(B);
                push(B.getRight());
                push(B.getLeft());
            }
        }
    };

    // Durchlaeuft den Baum in Levelorder
    // speichert hoechstens die Haelfte der Knoten in der Deque
    class LevelorderIterator extends TreeIterator{
        public LevelorderIterator(){
            if (root!=null) q.insertFirst(root);
        }
        public Object next(){
            if (!hasNext())
                throw new NoSuchElementException();
            TreeNode e = (TreeNode)q.removeLast();
            if (e.getLeft()!=null) q.insertFirst(e.getLeft());
            if (e.getRight()!=null) q.insertFirst(e.getRight());
            return e.getElement();
        }
    };

} // LinkedBinaryTree