public class BinarySearchTreeNode<T extends Comparable<T>> {
  protected T value;
  protected BinarySearchTreeNode<T> left;
  protected BinarySearchTreeNode<T> right;

  /**
   * Constructs a BinarySearchTreeNode with the given value.
   * 
   * @param value A value.
   */
  public BinarySearchTreeNode(T value) {
    this.value = value;
  }

  /**
   * Get the value.
   */
  public T get() {
    return value;
  }

  /**
   * Gets the left subtree.
   */
  public BinarySearchTreeNode<T> getLeft() {
    return left;
  }

  /**
   * Gets the right subtree.
   */
  public BinarySearchTreeNode<T> getRight() {
    return right;
  }

  /**
   * Sets the left subtree.
   * 
   * @param t A tree.
   */
  public void setLeft(BinarySearchTreeNode<T> t) {
    left = t;
  }

  /**
   * Sets the right subtree.
   * 
   * @param t A tree.
   */
  public void setRight(BinarySearchTreeNode<T> t) {
    right = t;
  }

  /**
   * Computes the number of nodes in the tree.
   */
  public int size() {
    int l = left != null ? left.size() : 0;
    int r = right != null ? right.size() : 0;
    return 1 + l + r;
  }

  /**
   * Returns a string representation of the tree.
   */
  public String toString() {
    // (v l r)
    if (left == null && right == null) {
      return value.toString();
    }
    String l = left != null ? left.toString() : "<e>";
    String r = right != null ? right.toString() : "<e>";
    return "(" + value.toString() + " " + l + " " + r + ")";
  }

  /**
   * Returns the edge height of the given tree.
   * 
   * @param t A tree or null for the empty tree.
   */
  public static <E extends Comparable<E>> int getHeight(BinarySearchTreeNode<E> t) {
    if (t == null) {
      return -1;
    }
    int lh = getHeight(t.getLeft());
    int rh = getHeight(t.getRight());
    return lh > rh ? lh + 1 : rh + 1;
  }

  /**
   * Inserts a value into the tree, preserving the binary
   * search property. Equal elements are stored in the
   * subtree to the right.
   * 
   * @param value A value to insert.
   */
  public void add(T value) {
    if (value.compareTo(this.value) < 0) {
      // on left
      if (left != null) {
        // something is already there
        left.add(value);
      } else {
        // nothing is there
        setLeft(new BinarySearchTreeNode<T>(value));
      }
    } else {
      // on right
      if (right != null) {
        // something is already there
        right.add(value);
      } else {
        // nothing is there
        setRight(new BinarySearchTreeNode<T>(value));
      }
    }
  }
}