Search in Code

The public method starts the search at the root:

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

The private helper searches the subtree rooted at the node it receives:

private boolean contains(Node<T> node, T value) {
  if (node == null) {
    return false;  // fell off the tree
  }

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

The helper is the search plan from the previous section, written in code. The base case node == null means the search fell off the tree, so the value is not present. Otherwise the sign of cmp says whether we found the value or which subtree could still hold it.

The iterative version is the same search with a current reference:

public boolean containsIterative(T value) {
  Node<T> current = root;
  while (current != null) {
    int cmp = value.compareTo(current.value);
    if (cmp == 0) {
      return true;
    } else if (cmp < 0) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return false;
}

The recursive version keeps the path on the call stack. The iterative version keeps only the next node in current.