import java.util.LinkedList;
public class Tree  {
    private Node root;
    public Tree() { 
        root = null; 
    }
    public boolean isEmpty() {  // O(1) time, O(1) space
        if (root == null) {
            return true;
        }
        else{
            return false;
        }
    }
    public void insert (int value){
        insertHelper(root,value);
    }
    private void insertHelper(Node x, int value) { // Average time is O (log n)  and worst case is O(n),  O(1) space
        if (x == null){
            root = new Node (value, null, null);
        }
        else {
            if ( value < x.getData()) {
                if ( x.getLeftNodeReference() == null ){
                    Node y = new Node( value, null, null );
                    x.setLeftNodeReference(y); 
                }
                else {
                    insertHelper(x.getLeftNodeReference(), value);
                }
            }
            else {
                if ( x.getRightNodeReference() == null) {
                    Node y = new Node( value, null, null );
                    x.setRightNodeReference(y); 
                }
                else {
                    insertHelper(x.getRightNodeReference(),value);
                }
            }
        }
    }
    public void LevelOrderTraversalBFS(Node x) { // O(N)
        LinkedList <Node> queue  = new LinkedList <Node>();
        if (x != null){
            queue.add(x);
        }
        int level = 0;
        while (!queue.isEmpty())  {
            level++;
            System.out.print ("Level#" + level + " :" );
            int size = queue.size();                    
            while ( size > 0){
                Node value = queue.poll();                  // removeFromFront()
                System.out.print (value.getData() + "   ");
                if (value.getLeftNodeReference() != null) {
                    queue.add(value.getLeftNodeReference());
                }
                if (value.getRightNodeReference() != null) {        // insertFromBack(Node)
                    queue.add(value.getRightNodeReference());   // insertFromBack(Node)
                }
                size--;
            }
            System.out.println();
        }
    }
    public void strictlyBinaryIterative()   { 
        System.out.println("Strictly Binary Iterative ");
        strictlyBinaryIterativeHelper(root); // O(N). O(N) space
    }
    private void strictlyBinaryIterativeHelper(Node x) {// BFS : Breadth First Search
        LinkedList <Node> queue = new LinkedList <Node>(); // LinkedList API, import java.util.LinkedList
        if (x != null){
            queue.add(x);
        }
        int count = 0, count1 = 0;
        while (!queue.isEmpty()){
            Node value = queue.poll(); // removeFromFront()
            if (value.getLeftNodeReference() != null || value.getRightNodeReference() != null){
                count++;
                if (value.getLeftNodeReference() != null && value.getRightNodeReference() != null){
                    count1++;
                    System.out.println ("Strictly Binary = " + value.getData() + " Count = " + count);
                }
            }
            if (value.getLeftNodeReference() != null) {
                queue.add(value.getLeftNodeReference());
            }
            if (value.getRightNodeReference() != null) {     // insertFromBack(Node)
                queue.add(value.getRightNodeReference());   // insertFromBack(Node)
            }
        }
        System.out.println ("Non-leaf Nodes = " + count);
        System.out.println ("Strictly Binary Nodes = " + count1);
        if (count == count1){
            System.out.println ("All non leaf nodes are strictly binary");
        }
        else if (count1 == 0){
            System.out.println ("None of the leaf nodes are strictly binary");
        }
        else{
            System.out.println ( count1 + " non leaf nodes are strictly binary");
        }
    }
    public void strictlyBinaryRecursive(){ // O(N), O(1) space
        System.out.println("Strictly Binary Recursive ");
        if (root == null){
            System.out.println ("Tree is Empty");
        }
        else{
            int count = countNonLeafNodesHelper(root);
            int count1 = strictlyBinaryRecursiveHelper(root);
            System.out.println ("Non-leaf Nodes = " + count);
            System.out.println ("Strictly Binary Nodes = " + count1);
            if (count == count1){
                System.out.println ("All non leaf nodes are strictly binary");
            }
            else if (count1 == 0){
                System.out.println ("None of the leaf nodes are strictly binary");
            }
            else{
                System.out.println ( count1 + " non leaf nodes are strictly binary");
            }
        }
    }
    private int countNonLeafNodesHelper(Node value){ // O(N) , O(1) space
        if ((value == null) || ((value.getLeftNodeReference() == null && value.getRightNodeReference() == null))){ // Leaf
            return 0;
        }
        else{ // Non-leaf
            int count = 1 +  countNonLeafNodesHelper(value.getLeftNodeReference()) +  countNonLeafNodesHelper(value.getRightNodeReference());
            System.out.println ("Non-leaf  = " + value.getData() + " Count = " + count);
            return count;
        }
    }
    private int strictlyBinaryRecursiveHelper(Node value){ // O(N), O(1) space
        if (value == null || (value.getLeftNodeReference() == null && value.getRightNodeReference() == null)){ // Leaf
            return 0;
        }
        // Non-leaf with one child
        else if ((value == null) || ((value.getLeftNodeReference() != null && value.getRightNodeReference() == null) || (value.getLeftNodeReference() == null && value.getRightNodeReference() != null))){
            return 0;
        }
        // Non-leaf with two children
        else{
            int count = 1 +  strictlyBinaryRecursiveHelper(value.getLeftNodeReference()) +  strictlyBinaryRecursiveHelper(value.getRightNodeReference());
            System.out.println ("Strictly Binary = " + value.getData() + " Count = " + count);
            return count;
        }
    }
    public void outputTree(){
        if (root == null){
            System.out.println ("Tree is empty");
        }
        else{
            outputTreeHelper(root, 0);
        }
    }
    private void outputTreeHelper( Node currentNode, int spaces)  { // O(n) time, O(1) space
        if (currentNode == null){
            return;
        }
        else { 
            outputTreeHelper( currentNode.getRightNodeReference(), spaces + 5 );
            for ( int k = 1; k <= spaces; k++ ){

                System.out.print(" ");
            }
            System.out.println( currentNode.getData() );
            outputTreeHelper( currentNode.getLeftNodeReference(), spaces + 5 );
        }
    }
}