import java.util.LinkedList;

public class Tree  {
    private Node root;

    public Tree() { 
        root = null; 
    }

    public boolean isEmpty() {  // O(1) time, O(1) spac
        if (root == null) {
            return true;
        }
        else{
            return false;
        }
    }

    public void insert(int value){
        insertHelper(value, root);
    }

    private void insertHelper(int value , Node x ) { // 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(value, x.getLeftNodeReference());
                }
            }
            else {
                if ( x.getRightNodeReference() == null) {
                    Node y = new Node( value, null, null );
                    x.setRightNodeReference(y); 
                }
                else {
                    insertHelper(value, x.getRightNodeReference());
                }
            }
        }
    }

    public void maxValue(){
        System.out.println ("Max value = " + maxValueHelper(root));
    }

    private int maxValueHelper (Node node)  {   // Average time is O (log n)  and worst case is O(n),  O(1) space
        if (node.getRightNodeReference() == null) {
            return (node.getData());
        }
        else  {
            return maxValueHelper(node.getRightNodeReference());
        }
    }

    public void minValue(){
        System.out.println ("Max value = " + minValueHelper(root));
    }

    private int minValueHelper(Node node) // Average time is O (log n)  and worst case is O(n),  O(1) space
    {
        if (node.getLeftNodeReference() != null){
            return minValueHelper(node.getLeftNodeReference());
        }
        else {
            return (node.getData());
        }
    }

    public void printAllLeaves(){
        printAllLeavesHelper(root);
    }

    private void  printAllLeavesHelper(Node node)   {//  O(n) time,  O(1) space
        if (node == null) {
            return;
        }
        else if (node.getRightNodeReference() == null && node.getLeftNodeReference() == null){

            System.out.println (node.getData());
        }
        else{
            printAllLeavesHelper(node.getLeftNodeReference());
            printAllLeavesHelper(node.getRightNodeReference());
        }
    }

    public void findValue (int value){
        int ans = findValueHelper(root,value);
        if (ans == 0){
            System.out.println (value + " is not found in the tree");
        }
        else {
            System.out.println (value + " is found in the tree");
        }
    }

    private int findValueHelper (Node node, int value)  {// Average time is O (log n)  and worst case is O(n),  O(1) space
        if (node == null) {
            return 0;
        }
        else if (node.getData() == value) {
            return 1;
        }
        else if (value < node.getData()) {
            return findValueHelper (node.getLeftNodeReference(), value);
        }
        else {
            return findValueHelper (node.getRightNodeReference(), value);
        }
    }

    public void outputTree(){
        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 );
        }
    }

    public int findLevel (int value) {    // Average time is O (log n)  and worst case is O(n),  O(1) space
        return findLevelHelper(root, value,0);
    }

    private int findLevelHelper (Node node, int value, int level){
        if (node == null){
            return -1;
        }
        else {
            level++;
            if (node.getData() == value){
                return level;
            }
            else if (value < node.getData()){
                return findLevelHelper(node.getLeftNodeReference(), value, level);
            }
            else {
                return findLevelHelper (node.getRightNodeReference(), value, level);
            }
        }
    }

    public void height (){
        System.out.println ("Height = " + heightHelper(root));
    }

    private int heightHelper (Node node){ // O(n) time, O(1) space
        if (node == null)   {
            return 0;
        }
        else{
            int l = 0, r = 0;
            l = 1 + heightHelper (node.getLeftNodeReference());
            r = 1 + heightHelper (node.getRightNodeReference());
            if (l > r)   {
                return l;
            }
            else {
                return r;
            }
        }
    }

    public void deepestLeaves() {
        deepestLeavesHelper(root);
    }

    private void deepestLeavesHelper(Node x)     {  // O(n2), O(1) space
        if (x == null)  {
            return;
        }
        else if (x.getLeftNodeReference() == null && x.getRightNodeReference() == null) {
            if (findLevelHelper (root, x.getData(), 0) == heightHelper (root))    {
                System.out.println(x.getData());
            }
        }
        else{
            deepestLeavesHelper (x.getLeftNodeReference());
            deepestLeavesHelper(x.getRightNodeReference());
        }
    }

    public void increasingOrder(Node x) {
        increasingOrderHelper(root);
    }

    public void increasingOrderHelper(Node x)  {  // O(n) time, O(1) space
        if (x == null) {
            return;
        }
        else {
            increasingOrderHelper (x.getLeftNodeReference());
            System.out.print (x.getData() + "  ");
            increasingOrderHelper(x.getRightNodeReference());
        }
    }
    // Method #1 : Average time is O (n2 log n) and worst case time is O (n3) , O (1) space

    public void printTreeByLevelHelper(){
        printTreeByLevelHelper1(root);
    }

    private void printTreeByLevelHelper1(Node x) {
        for (int i = 1; i <=heightHelper(x); i++) {
            System.out.print ("Level " + i + ": ");
            printByLevelHelper2 (x, i);
            System.out.println();
        }
    }

    private void printByLevelHelper2 (Node x, int y){
        if (x == null) {
            return;
        }
        else if (findLevelHelper(root, x.getData(),0) == y) {
            System.out.print(x.getData() + "   ");
        }
        else {
            printByLevelHelper2 (x.getLeftNodeReference(), y);
            printByLevelHelper2 (x.getRightNodeReference(), y);
        }
    }
    //  Method #2: O (n2) time, O (1) space

    public void printTreeByLevelOptimized(){
        printTreeByLevelOptimizedHelper1(root);
    }

    private void printTreeByLevelOptimizedHelper1(Node x) {
        for (int i = 1; i <=heightHelper(x); i++){
            System.out.print ("Level " + i + ": ");
            printTreeByLevelHelperOptimized2 (x, i);
            System.out.println();
        }
    }

    private void printTreeByLevelHelperOptimized2(Node x, int y)    {
        if (x == null){
            return;
        }
        else if (y == 1){
            System.out.print(x.getData() + "   ");
        }
        else {
            printByLevelHelper2 (x.getLeftNodeReference(), y-1);
            printByLevelHelper2 (x.getRightNodeReference(), y-1);
        }
    }
    //Method #3: O (n) time, O(n) space
    //Uses a LinkedList from the Java Collections API
    // import java.util.LinkedList
    public void printTreeByLevelIterative(){
        printTreeByLevelIterativeHelper(root);
    }

    private void printTreeByLevelIterativeHelper(Node node){
        LinkedList <Node> queue  = new LinkedList <Node>();
        queue.add(node);
        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();
        }
    }
}