public class Tree {
    class IntNode {

        // Do not change these variables and the constructor.  Do not add further variables and constructors here.
        private int elem;
        private IntNode left;
        private IntNode right;

        private IntNode(int elem) {
            this.elem = elem;
        }

        void add(int elem){
            if(elem< this.elem){ //it should be in the left part
                if(this.left==null){
                    this.left=new IntNode(elem);
                }else{
                    this.left.add(elem);
                }
            }else { //right subtree -> e >= this.elem
                if(this.right==null){
                    this.right=new IntNode(elem);
                }else {
                    this.right.add(elem);
                }
            }
        }

        private IntNode copyNode(){
            IntNode helpNode = new IntNode(this.elem);
            if(this.left!=null){
                helpNode.add(this.left.elem);
            }
            if(this.right!=null){
                helpNode.add(this.right.elem);
            }
            return helpNode;
        }

        int countLeaves(){
            int count = 0;
            if(this.left== null || this.right==null){
                return 1;
            }
            if(this.left!=null){
                count+= this.left.countLeaves();
            }
            if(this.right!=null){
                count+=this.right.countLeaves();
            }
            return count;
        }

        String toStringPrefix(){ //node, left, right
            String s = Integer.toString(elem);
            if(this.left!=null){
                s += " " + this.left + " ";
            }
            if(this.right!= null){
                s +=  this.right;
            }
            return s;
        }

        String toStringPostfix(){ //left,right, node
            String s = "";
            if(this.left!=null){
                s = this.left + " ";
            }
            if(this.right!= null){
                s+= " " +  this.right + " ";
            }
            s += Integer.toString(elem);
            return s;
        }

        @Override
        public String toString(){ //inorder - left, node, right
            String s = Integer.toString(elem);
            if(this.left!=null){
                s = this.left + "  " + s;
            }

            if(this.right!= null){
                s+=  " " + this.right ;
            }
            return s;
        }

        int maxDepth(){
            if(this.left== null && this.right==null){
                return 0;
            }
            int l = 0;
            int r = 0;

            if(this.left!= null){
                l = this.left.maxDepth();
            }
            if(this.right!=null){
                r = this.right.maxDepth();
            }

            return Math.max(l  ,r) + 1 ;
        }

        IntNode find(int elem){ //check
            IntNode helpNode = this;
            if(helpNode.elem == elem){
                return helpNode;
            }
            else if(elem < helpNode.elem){ //maybe the element is in the left subtree
                helpNode = helpNode.left;
            }else {
                helpNode = helpNode.right;
            }
            return helpNode;
        }

        /*
        SortedList toSortedList(){
            SortedList helpList = new SortedList();
            if(this.left!=null){
              helpList =   this.left.toSortedList();
            }
            helpList.addSorted(this.elem);
            if(this.right!= null){
               SortedList listRight =  this.right.toSortedList();
                SortedList.Node current = listRight.getHead();
                while(current!= null){
                    helpList.addSorted(current.getElem());
                    current = current.getNext();
                }
            }

            return helpList;
        } */

        // hashCode sollte hier zwar implementiert sein, geht aber nicht in die Beurteilung ein.
        @Override
        public int hashCode() {
            return 11111;
        }

    } // End of the definition of Node

    // The root of the tree.  Do not change or add object variables.
    private IntNode root = null;

    public boolean empty(){
        return this.root==null;
    }

    public void add(int elem){
        if(empty()){
            this.root = new IntNode(elem);
        }else {
            this.root.add(elem);
        }
    }

    public void remove(int elem){

    }

    public IntNode find(int elem){ //contains method
        //whether a Node is in the Tree or not
        //TODO returns the node where you found the element or null otherwise
       if(empty()){
           return null;
       }else {
           return root.find(elem);
       }
    }

    public int countLeaves(){
        //TODO returns the number of leaf-nodes in the whole tree
        if(empty()){
            return 0;
        }
        else {
            return this.root.countLeaves();
        }

    }

    public int maxDepth(){
        //TODO returns the maximum depth of a tree (root depth = 0)
        if(empty()){
            return 0;
        } else {
            return this.root.maxDepth();
        }
    }


    @Override
    public  String toString(){
        //TODO print INfix notation
        if(empty()) {
            return "";
        }
        return this.root.toString();
    }


    public String toStringPrefix(){
        //TODO print PREfix notation
        if(empty()) {
            return "";
        }
        return this.root.toStringPrefix();
    }


    public String toStringPostfix(){
        //TODO print POSTfix notation
        if(empty()){
            return "";
        }
        return this.root.toStringPostfix();
    }

    /*
    public SortedList toSortedList(){
        //TODO convert to a SortedList
        return root.toSortedList();
    }*/

    public IntNode copyTree(){
        if(empty()){
            return null;
        }else {
            return this.root.copyNode();
        }
    }



    // Just for testing, not used for assessment (geht nicht in die Beurteilung ein).
    public static void main(String[] args) {
        Tree myTree = new Tree();
        myTree.add(20);
        myTree.add(10);
        myTree.add(5);
        myTree.add(15);
        myTree.add(30);
        myTree.add(25);
        myTree.add(35);
        myTree.add(55);


        System.out.println(myTree);
        System.out.println();
        System.out.println(myTree.toStringPostfix());
        System.out.println();
        System.out.println(myTree.toStringPrefix());
        System.out.println();
        System.out.println(myTree.maxDepth());

        myTree.copyTree();
        System.out.println(myTree);
    }
}