public class BinarySearchTreeNode<K extends Comparable<K>, V> {
  protected K key;
  protected V value;
  protected BinarySearchTreeNode<K, V> left;
  protected BinarySearchTreeNode<K, V> right;

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

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

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

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

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

  /**
   * Sets the right subtree.
   * 
   * @param t A tree.
   */
  public void setRight(BinarySearchTreeNode<K, V> 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)
    String kv = key.toString() + ":" + value.toString();
    if (left == null && right == null) {
      return kv;
    }
    String l = left != null ? left.toString() : "<e>";
    String r = right != null ? right.toString() : "<e>";
    return "(" + kv + " " + 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>, F> int getHeight(BinarySearchTreeNode<E, F> 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(K key, V value) {
    if (key.compareTo(this.key) < 0) {
      // on left
      if (left != null) {
        // something is already there
        left.add(key, value);
      } else {
        // nothing is there
        setLeft(new BinarySearchTreeNode<K, V>(key, value));
      }
    } else {
      // on right
      if (right != null) {
        // something is already there
        right.add(key, value);
      } else {
        // nothing is there
        setRight(new BinarySearchTreeNode<K, V>(key, value));
      }
    }
  }

  /**
   * Returns the value if the tree contains the given key.
   * 
   * @param key A key to search the tree for.
   */
  public V find(K key) {
    if (key.compareTo(this.key) < 0) {
      // left
      if (left != null) {
        return left.find(key);
      } else {
        return null;
      }
    } else if (key.compareTo(this.key) > 0) {
      // right
      if (right != null) {
        return right.find(key);
      } else {
        return null;
      }
    } else {
      // it the one we were looking for
      return value;
    }
  }

  /**
   * Returns true iff the tree contains the key.
   * 
   * @param key A key to search the tree for.
   */
  public boolean contains(K key) {
    return find(key) != null;
  }
}