/**
 * Simplified class that implements a binary tree.
 *   @author Dave Reed
 *   @version 2/14/17
 */
public class BinaryTree<E> {
    protected TreeNode<E> root;

    /**
     * Constructs an empty binary tree.
     */
    public BinaryTree() {
        this.root = null;
    }

    /**
     * Adds a value to the binary tree.
     *   @param value the value to be added
     */
    public void add(E value) {
        this.root = this.add(this.root, value);
    }
    private TreeNode<E> add(TreeNode<E> current, E value) {
        if (current == null) {
            current = new TreeNode<E>(value, null, null);
        }
        else if (Math.random() <= 0.5) {
            current.setLeft(this.add(current.getLeft(), value));
        }
        else {
            current.setRight(this.add(current.getRight(), value));
        }
        return current;
    }

    /**
     * Determines whether a value is stored in the binary tree.
     *   @param value the desired value
     *   @return true if value is in the tree; else false
     */
    public boolean contains(E value) {
        return this.contains(this.root, value);
    }
    private  boolean contains(TreeNode<E> current, E value) {
        if (current == null) {
            return false;
        }
        else {
            return value.equals(current.getData()) ||
                   this.contains(current.getLeft(), value) ||
                   this.contains(current.getRight(), value);
        }
    }

    /**
     * Detemrines the size of the binary tree.
     *   @return the number of values stored in the tree
     */
    public int size() {
        return this.size(this.root);
    }
    private int size(TreeNode<E> current) {
        if (current == null) {
            return 0;
        }
        else {
            return this.size(current.getLeft()) +
                   this.size(current.getRight()) + 1;
        }
    }
    
    /**
     * Converts the binary tree into a string using inorder traversal.
     *   @return the string representation of the tree
     */
    public String toString() {
        if (this.root == null) {
            return "[]";
        }

        String recStr = this.toString(this.root);
        return "[" + recStr.substring(0,recStr.length()-1) + "]";
    }
    private String toString(TreeNode<E> current) {
        if (current ==  null) {
            return "";
        }

        return this.toString(current.getLeft()) +
               current.getData().toString() + "," +
               this.toString(current.getRight());
    }

    ////////////////////////////////////////////////////////////////////////

    protected class TreeNode<E> {
        private E data;
        private TreeNode<E> left;
        private TreeNode<E> right;

        public TreeNode(E d, TreeNode<E> l, TreeNode<E> r) {
            this.data = d;
            this.left = l;
            this.right = r;
        }

        public E getData() {
            return this.data;
        }

        public TreeNode<E> getLeft() {
            return this.left;
        }

        public TreeNode<E> getRight() {
            return this.right;
        }

        public void setData(E newData) {
            this.data = newData;
        }

        public void setLeft(TreeNode<E> newLeft) {
            this.left = newLeft;
        }

        public void setRight(TreeNode<E> newRight) {
            this.right = newRight;
        }
    }

//    public static void main(String[] args) {
//        BinaryTree<Integer> tree = new BinaryTree<Integer>();
//        tree.add(7);
//        tree.add(2);
//        tree.add(12);
//        tree.add(1);
//        tree.add(5);
//        tree.add(6);
//        tree.add(99);
//        tree.add(88);
//
//        System.out.println(tree);
//        System.out.println("size = " + tree.size());
//        System.out.println(tree.contains(5) + " " + tree.contains(8));
//    }
}