package bst;

public class BinarySearchTree<E extends Comparable<? super E>> {
    BinaryNode<E> root;
    int size;

    /**
     * Constructs an empty binary search tree.
     */
    public BinarySearchTree() {

    }

    /**
     * Inserts the specified element in the tree if no duplicate exists.
     * @param x element to be inserted
     * @return true if the the element was inserted
     */
    public boolean add(E x) {
        if(root == null) {
            root = new BinaryNode<E>(x);
            size++;
            return true;
        } else {
            return add(root, x);
        }
    }

    private boolean add(BinaryNode<E> node, E item) {
        int compResult = item.compareTo(node.element);
        if(compResult == 0) {
            return false;
        }

        if(compResult < 0) {
            if(node.left == null) {
                node.left = new BinaryNode<E>(item);
                size++;
                return true;
            } else {
                return add(node.left, item);
            }
        } else {
            if(node.right == null) {
                node.right = new BinaryNode<E>(item);
                size++;
                return true;
            } else {
                return add(node.right, item);
            }
        }
    }

    /**
     * Computes the height of tree.
     * @return the height of the tree
     */
    public int height() {
        return height(root);
    }

    private int height(BinaryNode<E> node) {
        if(node == null) {
            return 0;
        } else {
            int left = 1 + height(node.left) ;
            int right = 1 + height(node.right);
            return (left < right) ? right : left;
        }
    }

    /**
     * Returns the number of elements in this tree.
     * @return the number of elements in this tree
     */
    public int size() {
        return size;
    }

    /**
     * Print tree contents in inorder.
     */
    public void printTree() {
        printTree(root);
    }

    private void printTree(BinaryNode<E> node) {
        if(node == null) {
            return;
        } else {
            printTree(node.left);
            System.out.print(node.element);
            printTree(node.right);
        }
    }

    /**
     * Builds a complete tree from the elements in the tree.
     */
    public void rebuild() {
        @SuppressWarnings("unchecked")
        E[] a = (E[]) new Comparable[size];
        root = buildTree(a, 0, toArray(root, a, 0)-1);
    }

    /**
     * Adds all elements from the tree rooted at n in inorder to the array a
     * starting at a[index].
     * Returns the index of the last inserted element + 1 (the first empty
     * position in a).
     */
    private int toArray(BinaryNode<E> n, E[] a, int index) {
        if(n != null) {
            index = toArray(n.left, a, index);
            a[index++] = n.element;
            index = toArray(n.right, a, index);
            return index;
        }
        return index;
    }

    /**
     * Builds a complete tree from the elements a[first]..a[last].
     * Elements in the array a are assumed to be in ascending order.
     * Returns the root of tree.
     */
    private BinaryNode<E> buildTree(E[] a, int first, int last) {
        int mid = ((last + first) / 2);

        if(last == first) {
            return new BinaryNode<E>(a[mid]);
        } else if (first > last) {
            return null;
        }

        BinaryNode<E> temp = new BinaryNode<E>(a[mid]);
        temp.left = buildTree(a, first, mid-1);

        mid = ((last + first) / 2);

        temp.right = buildTree(a, mid+1, last);

        return temp;
    }



    static class BinaryNode<E> {
        E element;
        BinaryNode<E> left;
        BinaryNode<E> right;

        private BinaryNode(E element) {
            this.element = element;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bintre = new BinarySearchTree<Integer>();
        bintre.add(1);
        bintre.add(3);
        bintre.add(5);
        bintre.add(7);
        bintre.add(9);
        bintre.add(11);
        bintre.add(13);

        bintre.rebuild();
        BSTVisualizer draw = new BSTVisualizer("Window", 600, 600);
        draw.drawTree(bintre);

    }
}