/**
 * A binary search tree (BST) is a sorted ADT that uses a binary
 * tree to keep all elements in sorted order.  If the tree is
 * balanced, performance is very good: O(lg n) for most operations.
 * If unbalanced, it performs more like a linked list: O(n).
 *
 * @author Zach Tomaszewski
 */
public class BinarySearchTree<E extends Comparable<E>> {

  private TreeNode<E> root = null;
  private int size = 0;

  /** Creates an empty tree. */
  public BinarySearchTree() {
  }


  /** Returns whether this BST contains the given item. */
  public boolean contains(E item) {
    TreeNode<E> curr = this.root;
    while(curr != null) {
      if (item.compareTo(curr.getData()) < 0) {
        curr = curr.getLeft();
      }else if (item.compareTo(curr.getData()) > 0) {
        curr = curr.getRight();
      }else {
        //found it
        return true;
      }
    }
    return false;  //did not find it
  }


  /** Adds the given item to this BST. */
  public void add(E item) {
    this.root = add(item, root);
    this.size++;
  }

  private TreeNode<E> add(E item, TreeNode<E> subtree) {
    if (subtree == null) {
      return new TreeNode<E>(item);
    }else {
      if (item.compareTo(subtree.getData()) <= 0) {
        subtree.setLeft(add(item, subtree.getLeft()));
      }else {
        subtree.setRight(add(item, subtree.getRight()));
      }
      return subtree;
    }
  }

  /** Returns the greatest (earliest right-most node) of the given tree. */
  private E findMax(TreeNode<E> n) {
    if (n == null) {
      return null;
    }else if (n.getRight() == null) {
      //can't go right any more, so this is max value
      return n.getData();
    }else {
      return findMax(n.getRight());
    }
  }

  /**
   * Returns item from tree that is equivalent (according to compareTo)
   * to the given item.  If item is not in tree, returns null.
   */
  public E get(E item) {
    return get(item, this.root);
  }

  /** Finds it in the subtree rooted at the given node. */
  private E get(E item, TreeNode<E> node) {
    if (node == null) {
      return null;
    }else if (item.compareTo(node.getData()) < 0) {
      return get(item, node.getLeft());
    }else if (item.compareTo(node.getData()) > 0) {
      return get(item, node.getRight());
    }else {
      //found it!
      return node.getData();
    }
  }

  /**
   * Removes the first equivalent item found in the tree.
   * If item does not exist to be removed, throws IllegalArgumentException().
   */
  public void remove(E item) {
    this.root = remove(item, this.root);
  }

  private TreeNode<E> remove(E item, TreeNode<E> node) {
    if (node == null) {
      //didn't find item
      throw new IllegalArgumentException(item + " not found in tree.");
    }else if (item.compareTo(node.getData()) < 0) {
      //go to left, saving resulting changes made to left tree
      node.setLeft(remove(item, node.getLeft()));
      return node;
    }else if (item.compareTo(node.getData()) > 0) {
      //go to right, saving any resulting changes
      node.setRight(remove(item, node.getRight()));
      return node;
    }else {
      //found node to be removed!
      if (node.getLeft() == null && node.getRight() == null) {
        //leaf node
        return null;
      }else if (node.getRight() == null) {
        //has only a left child
        return node.getLeft();
      }else if (node.getLeft() == null) {
        //has only a right child
        return node.getRight();
      }else {
        //two children, so replace the contents of this node with max of left tree
        E max = findMax(node.getLeft());  //get max value
        node.setLeft(remove(max, node.getLeft())); //and remove its node from tree
        node.setData(max);
        return node;
      }
    }
  }

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

  /**
   * Returns a single-line representation of this BST's contents.
   * Specifically, this is a comma-separated list of all elements in their
   * natural Comparable ordering.  The list is surrounded by [] characters.
   */
  @Override
  public String toString() {
    return "[" + toString(this.root) + "]";
  }

  private String toString(TreeNode<E> n) {
    //would have been simpler to use Iterator... but not implemented yet.
    if (n == null) {
      return "";
    }else {
      String str = "";
      str += toString(n.getLeft());
      if (!str.isEmpty()) {
        str += ", ";
      }
      str += n.getData();
      if (n.getRight() != null) {
        str += ", ";
        str += toString(n.getRight());
      }
      return str;
    }
  }
}