package bst;

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) {
		int counter = size;
		root = add(root, x);
		return counter != size;
	}

	private BinaryNode<E> add(BinaryNode<E> node, E x) {
		if (node == null) {
			size++;
			return new BinaryNode<E>(x);
		} else if (x.compareTo(node.element) > 0) {
			node.right = add(node.right, x);
			return node;
		} else if (x.compareTo(node.element) < 0) {
			node.left = add(node.left, x);
			return node;
		}
		return node;
	}

	/**
	 * 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);

			if (left >= right) {
				return left;
			}
			return right;
		}
	}

	/**
	 * 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) {
			printTree(node.left);
			System.out.print(node.element + " ");
			printTree(node.right);
		}
	}

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

	/*
	 * 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) {
		return 0;
	}

	/*
	 * 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) {
		return null;
	}

	static class BinaryNode<E extends Comparable<? super E>> {
		E element;
		BinaryNode<E> left;
		BinaryNode<E> right;

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

	}

}