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