// alberi binari

import java.util.Random;
// classe per gli alberi binari
public class T {
    protected int root;
    protected T left;
    protected T right;

    public T(int root, T left, T right) {
        this.root = root;
        this.left = left;
        this.right = right;
    }

    public int root() {
        return root;
    }

    public T left() {
        return left;
    }

    public T right() {
        return right;
    }

    public String toString() {
        return toStringAux("");
    }

    private String toStringAux(String shift) {
        if (left == null && right == null) {
            return shift + root;
        } else if (left == null) {
            return shift + root + " <"
                    + "\n" + right.toStringAux(shift + "\t");
        } else if (right == null) {
            return left.toStringAux(shift + "\t") + "\n" + shift
                    + root + " <";
        } else {
            return left.toStringAux(shift + "\t") + "\n" + shift
                    + root + " <"
                    + "\n" + right.toStringAux(shift + "\t");
        }
    }

    public String albero() {
        return tostr("");
    }

    private String tostr(String ind) {
        String z = ind + "|--";
        if (left == null && right == null) {
            return "" + root;
        } else if (left != null && right == null) {
            return "" + root + "\n" + z +
                    left.tostr(ind + "|  ") + "\n" + z;
        } else if (left == null && right != null) {
            return "" + root + "\n" + z + "\n" + z +
                    right.tostr(ind + "   ");
        } else {
            return "" + root + "\n" + z + left.tostr(ind + "|  ")
                    + "\n" + z + right.tostr(ind + "   ");
        }
    }

    // restituisce la rappresentazione come stringa
// facendo una visita anticipata
    public String convert(){
        return convert("  ");
    }

    private String convert(String ind) {
        if (left == null && right == null) {
            return "T[" + root + ",null,null]";
        } else if (left != null && right == null) {
            return "T[" + root + "\n" + ind +
                    left.convert("   " + ind) + "\n" + ind + "null\n" + ind +
                    "\b\b\b]";
        } else if (left == null && right != null) {
            return "T[" + root + "\n" + ind + "null\n" + ind +
                    right.convert("   " + ind) + "\n" + ind + "\b\b\b]";
        } else {
            return "T[" + root + "\n" + ind + left.convert("   " + ind)
                    + "\n" + ind + right.convert("   " + ind) + "\n" + ind +
                    "\b\b\b]";
        }
    }


    // calcola l'altezza dell'albero
    public int height() {
        int leftHeight = 0, rightHeight = 0;

        if (left != null) {
            leftHeight = left.height();
        }
        if (right != null) {
            rightHeight = right.height();
        }

        if (leftHeight > rightHeight) {
            return 1 + leftHeight;
        } else {
            return 1 + rightHeight;
        }
    }

    // somma i nodi dell'albero
    public int add() {
        if (left == null && right == null) {
            return root;
        } else if (left == null) {
            return root + right.add();
        } else if (right == null) {
            return root + left.add();
        } else {
            return root + left.add() + right.add();
        }
    }

    // incrementa di uno i valori sui nodi
    public void incrementa() {
        root++;

        if (left != null) {
            left.incrementa();
        }
        if (right != null) {
            right.incrementa();
        }
    }

    // restituisce il valore minimo nell'albero
    public int getMin() {
        int leftMin, rightMin;

        if (left != null) {
            leftMin = left.getMin();
        } else {
            leftMin = root;
        }

        if (right != null) {
            rightMin = right.getMin();
        } else {
            rightMin = root;
        }

        if (root <= leftMin && root <= rightMin) {
            return root;
        } else if (leftMin <= root && leftMin <= rightMin) {
            return leftMin;
        } else {
            return rightMin;
        }
    }

    // sposta il minimo sulla radice. Gli altri numeri interi possono
    // essere spostati a piacimento ma non devono scomparire
    // dall'albero!
    public void moveMin() {
        int temp;

        if (left == null && right == null) {
            return;
        } else if (left == null) {
            right.moveMin();

            if (right.root < root) {
                temp = right.root;
                right.root = root;
                root = temp;
            }
        } else if (right == null) {
            left.moveMin();

            if (left.root < root) {
                temp = left.root;
                left.root = root;
                root = temp;
            }
        } else {
            left.moveMin();
            right.moveMin();

            if (left.root < root && left.root <= right.root) {
                temp = left.root;
                left.root = root;
                root = temp;
            } else if (right.root < root && right.root <= left.root) {
                temp = right.root;
                right.root = root;
                root = temp;
            }
        }
    }

    // crea una copia dell'albero
    public Object clone() {
        if (left == null && right == null) {
            return new T(root, null, null);
        } else if (left != null && right == null) {
            return new T(root, (T) (left.clone()), null);
        } else if (left == null && right != null) {
            return new T(root, null, (T) (right.clone()));
        } else {
            return new T(root, (T) (left.clone()), (T) (right.clone()));
        }
    }

    // cerca la chiave nell'albero con una visita
    // sinistra-destra-radice
    public boolean contains_sdr(int key) {
        if (left != null && left.contains_sdr(key)) {
            return true;
        } else if (right != null && right.contains_sdr(key)) {
            return true;
        } else {
            return key == root;
        }
    }

    // cerca la chiave nell'albero con una visita
    // radice-destra-sinistra
    public boolean contains_rds(int key) {
        if (key == root) {
            return true;
        } else if (right != null && right.contains_rds(key)) {
            return true;
        } else {
            return left != null && left.contains_rds(key);
        }
    }

    // restituisce la lista delle foglie dell'albero,
    // visitandoli nell'ordine sinistra-destra
    public L leaves() {
        if (left == null && right == null) {
            return new L(root, null);
        } else if (left == null) {
            return right.leaves();
        } else if (right == null) {
            return left.leaves();
        } else {
            return left.leaves().append(right.leaves());
        }
    }

    private static Random ran = new Random();

    // crea un albero di altezza indicata con numeri a caso nei nodi
    public static T casual(int height) {
        if (height == 1) {
            return new T(ran.nextInt(100), null, null);
        } else {
            return new T
                    (ran.nextInt(100), casual(height - 1), casual(height - 1));
        }
    }
}