package bst;

import java.util.ArrayList;

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

    /**
     * Constructs an empty binary searchtree.
     */
    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    /**
     * 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) {
        root = addNode(root, x);
        return true;
    }

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

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

    private BinaryNode<E> addNode(BinaryNode<E> node, E x) {

        if(node == null) {
            size++;
            return new BinaryNode<E>(x);
        }

        if(node.element.compareTo(x) == 1) {
            node.left = addNode(node.left, x);
        } else if(node.element.compareTo(x) == -1){
            node.right = addNode(node.right, x);
        }

        return node;

    }

    private int getHeight(BinaryNode<E> node) {

        if(node == null) {
            return 0;
        }

        int rh = getHeight(node.right);
        int lh = getHeight(node.left);

        return Math.max(rh + 1, lh + 1);

    }

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

    private void print(BinaryNode<E> node) {

        if(node == null) return;

        print(node.left);
        System.out.println(node.element);
        print(node.right);

    }

    /**
     * Builds a complete tree from the elements in the tree.
     */
    public void rebuild() {

        ArrayList<E> a = (ArrayList<E>) new ArrayList<Comparable>();

        toArray(root, a);

        root = buildTree(a);

    }

    /*
     * 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 void toArray(BinaryNode<E> n, ArrayList<E> a) {

        if(n == null) return;

        toArray(n.left, a);
        a.add(n.element);
        toArray(n.right, a);
    }

    /*
     * 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(ArrayList<E> a) {

        if(a.size() == 0) return null;

        int m = a.size()/2;
        BinaryNode<E> temp = new BinaryNode<E>(a.get(m));

        if(a.size() > 1) {
            temp.left = buildTree(new ArrayList<E>(a.subList(0, m)));
            temp.right = buildTree(new ArrayList<E>(a.subList(m+1, a.size())));
        }

        return temp;
    }


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

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

}