Remove in Code

Like add, removal uses a helper that returns the new root of the subtree, and the public method stores the result in root:

public void remove(T value) {
  root = remove(root, value);
}

Here is the helper:

private Node<T> remove(Node<T> node, T value) {
  if (node == null) {
    return null;
  }

  int cmp = value.compareTo(node.value);
  if (cmp < 0) {
    node.left = remove(node.left, value);
    return node;
  } else if (cmp > 0) {
    node.right = remove(node.right, value);
    return node;
  }

  if (node.left == null) {
    return node.right;
  } else if (node.right == null) {
    return node.left;
  } else {
    Node<T> successor = minNode(node.right);
    node.value = successor.value;
    node.right = remove(node.right, successor.value);
    return node;
  }
}

The first part is the search code, with the same assignment we used in add. The recursive call removes the value from one subtree, and the result is stored back into node.left or node.right.

When cmp == 0, the node holds the value to remove. The first branch handles two cases at once. If the node is a leaf, node.right is also null, so returning it removes the leaf. If the node has only a right child, returning node.right promotes that child. The second branch does the same for a node with only a left child and promotes that child.

If we get past those two checks, the node has two children. The else branch follows the three steps from the section on removing a two-child node. First, find the successor with minNode, which we wrote in the section on the minimum, maximum, and successor. Next, copy its value into this node. Then remove the old successor from the right subtree. That last call reuses remove itself. The successor has no left child, so the recursive removal ends in the first branch. node.right is never null in this branch, so the assumption in minNode holds here.