add, Recursively

The public method starts the recursion at the root:

@Override
public void add(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  size++;
  root = add(root, item, pathTo(size), 0);
}

After size++, the new element’s position is size, so pathTo(size) is the path to the open slot.

The helper follows the path one step per call:

// Attaches a new node holding item at the end of path, below node, and
// swims it up on the way back. index is the next step of path to take.
// Returns the root of the subtree.
private Node<T> add(Node<T> node, T item, String path, int index) {
  if (index == path.length()) {
    return new Node<>(item);  // the open slot
  }
  if (path.charAt(index) == '0') {
    node.left = add(node.left, item, path, index + 1);
    swimStep(node, node.left);
  } else {
    node.right = add(node.right, item, path, index + 1);
    swimStep(node, node.right);
  }
  return node;
}

The first add reaches the base case at once. The heap is empty, size becomes 1, and pathTo(1) is the empty string, so the helper returns the new node, and it becomes the root.

One step of swim

After storing the child, each call does one step of swim:

// Swaps the values of parent and child if the child outranks the parent.
private void swimStep(Node<T> parent, Node<T> child) {
  if (compare(child.value, parent.value) < 0) {
    swapValues(parent, child);
  }
}

Why is this enough? When the call below returns, its subtree is a valid heap, so the only place order can be wrong is between node and that child. A swap there leaves the child’s subtree valid, because the value that moves down ranks at least as high as everything that was below it.

Every call on the path checks its child, even after the value has stopped moving up. Those later checks find nothing to swap. Once a value fails to move up, the nodes above it have not changed, and each one already ranks at least as high as its child.

Swap values, not nodes

Here is swapValues:

// Exchanges the values of nodes a and b. The nodes stay where they are.
private void swapValues(Node<T> a, Node<T> b) {
  T temp = a.value;
  a.value = b.value;
  b.value = temp;
}

We could instead swap the nodes themselves, relinking them in the tree. Then the parent above them, and the children below them, would all have to be repointed, and sometimes root as well. Swapping values changes no reference, so the tree’s shape stays exactly as add built it.

The cost

The recursion makes one call per digit of the path, about $lo g n$ calls, and each call does a constant amount of work: one comparison and at most one swap. So add is $O (lo g n)$ . The call stack is also about $lo g n$ frames deep while it runs.