public class BinarySearchTreeNode> { protected T value; protected BinarySearchTreeNode left; protected BinarySearchTreeNode 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 getLeft() { return left; } /** * Gets the right subtree. */ public BinarySearchTreeNode getRight() { return right; } /** * Sets the left subtree. * * @param t A tree. */ public void setLeft(BinarySearchTreeNode t) { left = t; } /** * Sets the right subtree. * * @param t A tree. */ public void setRight(BinarySearchTreeNode 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() : ""; String r = right != null ? right.toString() : ""; 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 > int getHeight(BinarySearchTreeNode 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(value)); } } else { // on right if (right != null) { // something is already there right.add(value); } else { // nothing is there setRight(new BinarySearchTreeNode(value)); } } } }