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 );
        }
    }
}