Add in Code

The public method starts at the root, but it also has to update the root:

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

If the tree is empty, root is null, and adding the first value creates a new root. The helper returns the root of the subtree it was asked to add into:

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;
}

The base case is an empty subtree: the call that reaches null creates the new node and returns it. The recursive cases look like search, except that each one stores the result back into node.left or node.right. That assignment links the new node into the tree. Every call except the one that received null returns the node it received, so above the new leaf each assignment stores back the child that was already there.

If we try to add a duplicate, cmp == 0, neither branch runs, and the method returns node unchanged.

You can also write insertion iteratively by descending with both a current reference and a parent reference. When current becomes null, comparing the value with parent.value tells you whether to set parent.left or parent.right. The recursive version handles the parent tracking through the return value.