Implementing the Operations

Here is a binary search tree of Comparable values. Each public method starts at root and calls a private recursive helper with the same name. The tree stores no duplicates and no null values. add does nothing if the value is already in the tree, and remove does nothing if the value is not in the tree. A node with two children is removed by copying its in-order successor’s value into it and then removing the successor.

public class BinarySearchTree<T extends Comparable<T>> {
  private Node<T> root;

  private static class Node<T> {
    T value;
    Node<T> left;
    Node<T> right;

    Node(T value) {
      this.value = value;
    }
  }

  public boolean contains(T value) {
    return contains(root, value);
  }

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

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

  // Assumes node is not null. Returns the node with the smallest value in
  // the subtree rooted at node.
  private Node<T> minNode(Node<T> node) {
    while (node.left != null) {
      node = node.left;
    }
    return node;
  }
}
Solution
private boolean contains(Node<T> node, T value) {
  if (node == null) {
    return false;
  }

  int cmp = value.compareTo(node.value);
  if (cmp == 0) {
    return true;
  } else if (cmp < 0) {
    return contains(node.left, value);
  } else {
    return contains(node.right, value);
  }
}
Solution
private Node<T> add(Node<T> node, T value) {
  if (node == null) {
    return new Node<>(value);
  }

  int cmp = value.compareTo(node.value);
  if (cmp < 0) {
    node.left = add(node.left, value);
  } else if (cmp > 0) {
    node.right = add(node.right, value);
  }
  return node;
}
Solution
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;
  }
}
Solution

A call has no reference to the node above it, so it cannot change the link that points to its own node. Instead, it returns the root of its subtree after the change, and the caller stores that in node.left or node.right. In add, the call that reaches null returns the new node; in remove, the call that unlinks a leaf or a one-child node returns null or the only child. When the change happens at the root, such as adding to an empty tree or removing a root that has at most one child, the public method stores the result in root.