import java.rmi.registry.LocateRegistry;

public class BTree<E> {

    public BNode<E> root;

    public BTree() {
        root = null;
    }

    public BTree(E info) {
        root = new BNode<E>(info);
    }

    public void makeRoot(E elem) {
        root = new BNode<E>(elem);
    }

    public BNode<E> addChild(BNode<E> node, int where, E elem) {

        BNode<E> tmp = new BNode<E>(elem, node);

        if (where == BNode.LEFT) {
            if (node.left != null)  // veke postoi element
                return null;
            node.left = tmp;
        } else {
            if (node.right != null) // veke postoi element
                return null;
            node.right = tmp;
        }

        return tmp;
    }

    public void inorder() {
        System.out.print("INORDER: ");
        inorderR(root);
        System.out.println();
    }

    public void inorderR(BNode<E> n) {
        if (n != null) {
            inorderR(n.left);
            System.out.print(n.info.toString()+" ");
            inorderR(n.right);
        }
    }

    public void preorder() {
        System.out.print("PREORDER: ");
        preorderR(root);
        System.out.println();
    }

    public void preorderR(BNode<E> n) {
        if (n != null) {
            System.out.print(n.info.toString()+" ");
            preorderR(n.left);
            preorderR(n.right);
        }
    }

    public void postorder() {
        System.out.print("POSTORDER: ");
        postorderR(root);
        System.out.println();
    }

    public void postorderR(BNode<E> n) {
        if (n != null) {
            postorderR(n.left);
            postorderR(n.right);
            System.out.print(n.info.toString()+" ");
        }
    }

    public void inorderNonRecursive() {
        ArrayStack<BNode<E>> s = new ArrayStack<BNode<E>>(100);
        BNode<E> p = root;
        System.out.print("INORDER (nonrecursive): ");

        while (true) {
            // pridvizuvanje do kraj vo leva nasoka pri sto site koreni
            // na potstebla se dodavaat vo magacin za podocnezna obrabotka
            while (p != null) {
                s.push(p);
                p = p.left;
            }

            // ako magacinot e prazen znaci deka stebloto e celosno izminato
            if (s.isEmpty())
                break;

            p = s.peek();
            // pecatenje (obrabotka) na jazelot na vrvot od magacinot
            System.out.print(p.info.toString()+" ");
            // brisenje na obraboteniot jazel od magacinot
            s.pop();
            // pridvizuvanje vo desno od obraboteniot jazel i povtoruvanje na
            // postapkata za desnoto potsteblo na jazelot
            p = p.right;

        }
        System.out.println();

    }

    int insideNodesR(BNode<E> node) {
        if (node == null)
            return 0;

        if ((node.left == null)&&(node.right == null))
            return 0;

        return insideNodesR(node.left) + insideNodesR(node.right) + 1;
    }

    int listoviR(BNode<E> node) {
        if (node == null)
            return 0;

        if ((node.left == null)&&(node.right == null))
            return 1;  // ova e list, nema deca

        //ako ne e list, ke vleze vo sledno:
        return insideNodesR(node.left) + insideNodesR(node.right);
    }

    int dlabocinaR(BNode<E> node) {
        if (node == null)
            return 0;

        if ((node.left == null)&&(node.right == null))
            return 1;  // ova e list, nema deca

        //ako ne e list, ke presmeta max dlabocina od levo i desno
        return Math.max(dlabocinaR(node.left) ,
                dlabocinaR(node.right))+1;
    }


    public int insideNodes() {
        return listoviR(root);
    }

    int leavesR(BNode<E> node) {
        if (node != null) {
            if ((node.left == null)&&(node.right == null))
                return 1;
            else
                return (leavesR(node.left) + leavesR(node.right));
        } else {
            return 0;
        }
    }

    public int leaves() {
        return leavesR(root);
    }

    int depthR(BNode<E> node) {
        if (node == null)
            return 0;
        if ((node.left == null)&&(node.right == null))
            return 0;
        return (1 + Math.max(depthR(node.left), depthR(node.right)));
    }

    public int depth() {
        return depthR(root);
    }

    void mirrorR(BNode<E> node) {
        BNode<E> tmp;

        if (node == null)
            return;

        // simetricno preslikuvanje na levoto i desnoto potsteblo
        mirrorR(node.left);
        mirrorR(node.right);

        // smena na ulogite na pokazuvacite na momentalniot jazel
        tmp = node.left;
        node.left = node.right;
        node.right = tmp;

    }

    private BNode<E> findR(BNode<E> node, E what){

        if (node==null){  //ako ne postoi jazol, vrati null
            return null;
        }

        // ako si go nasol toa sto go baras, vrati go jazolot
        if(node.info.equals(what)){
            return node;
        }

        //baraj levo
        BNode<E> found=findR(node.left, what);
        if(found!=null){  //ako si go nasol levo
            return found; //vrati go
        }

        //baraj desno
        found=findR(node.right, what);
        if(found!=null) { //ako si go nasol desno
            return found; //vrati go

        }
        return null; //go nema kaj nas i kaj nasite deca, vrati null

    }

    public void preorderIterative(){
        //inorder:  koren, levo, desno

        BNode<E> current=root;

        ArrayStack<BNode<E>> stack= new ArrayStack<BNode<E>>(100);

        stack.push(current);
        while (!stack.isEmpty()){


            current=stack.pop();
            System.out.println(current.info.toString());//printaj go momentalniot
            //prvo desno
            if(current.right!=null){
                stack.push(current.right);
            }
            //pa levo, zatoa sto sledniot stack pop ke go izvadi prvo posledniot
            if(current.left!=null){
                stack.push(current.left);
            }
        }
    }

    public BNode<E> find(E what){
        return findR(root,what);
    }

    public void mirror() {
        mirrorR(root);
    }

    public int dijametar() {
        return dijametarR(root);
    }
    public int visina(BNode<E> node) {
        if(node == null) {
            return 0;
        }
        return Math.max(visina(node.left), visina(node.right)) + 1;
    }

    public int dijametarR(BNode<E> node) {
        if(node == null) {
            return 0;
        }

        int leftVisina = visina(node.left);
        int rightVisina = visina(node.right);

        int leftDijametar = dijametarR(node.left);
        int rightDijametar = dijametarR(node.right);

        return Math.max(Math.max(leftDijametar, rightDijametar), leftVisina + rightVisina + 1);

    }

    public int countFullNodesRec(BNode<E> node) {
        if(node == null) {
            return 0;
        }
        int res = 0;
        if(node.left != null && node.right != null) {
            res = 1;
        }
        return res + countFullNodesRec(node.left) + countFullNodesRec(node.right);
    }

    public int countFullNode() {
        return countFullNodesRec(root);
    }

    public void ZigZag() {
        if(root == null) {
            return;
        }

        ArrayStack<BNode<E>> level = new ArrayStack<>(100);
        ArrayStack<BNode<E>> nextLevel = new ArrayStack<>(100);

        level.push(root);
        boolean leftToRight = true;
        while(!level.isEmpty()) {
            BNode<E> node = level.pop();
            System.out.print(node.info + " ");

            if(leftToRight) {
                if(node.left != null) {
                    nextLevel.push(node.left);
                }
                if(node.right != null) {
                    nextLevel.push(node.right);
                }
            }
            else {
                if(node.right != null) {
                    nextLevel.push(node.right);
                }
                if(node.left != null) {
                    nextLevel.push(node.left);
                }
            }

            if(level.isEmpty()) {
                leftToRight = !leftToRight;
                ArrayStack<BNode<E>> tmp = level;
                level = nextLevel;
                nextLevel = tmp;
                System.out.println();

            }
        }
    }

    public BNode<E> LCA(E A, E B) {
        return LCArec(root, A, B);
    }

    private LCArec(BNode<E> node, E A, E B) {
        if(node == null) {
            return null;
        }

        if(node.info.equals(A) || node.info.equals(B)) {
            return node;
        }

        BNode<E> leftSearch = LCARec(node.left, A, B);
        BNode<E> rightSearch = LCArec(node.right, A, B);

        if(leftSearch != null && rightSearch != null) {
            return node;
        }

        if(leftSearch != null) {
            return leftSearch;
        }
        return rightSearch;


    }

    public boolean isBalanced() {
        return isBalanced(root);
    }

    private boolean isBalanced(BNode<E> node) {
        if(node == null) {
            return true;
        }
        int l = depthR(node.left);
        int r = depthR(node.right);

        if(Math.abs(l - r) <= 1 && isBalanced(node.left) && isBalanced(node.right)) {
            return true;
        }
        return false;
    }

}