Implementing get and containsKey

get and containsKey both search the tree by key. The search tree’s contains already did this search, but it only answered yes or no, and get needs the value stored under the key. So we write the recursive search to return the node that holds the key, and let each public method read what it needs from that node:

// Returns the node holding key in the subtree rooted at node, or null if
// key is not there.
private Node<K, V> find(Node<K, V> node, K key) {
  if (node == null) {
    return null;
  }

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

Both public methods reject a null key, as the Map contract asks. get returns the found node’s value, or null when the key is absent:

@Override
public V get(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  Node<K, V> node = find(root, key);
  if (node == null) {
    return null;
  }
  return node.value;
}

containsKey runs the same search and reports whether find returns a node:

@Override
public boolean containsKey(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  return find(root, key) != null;
}

get and containsKey follow a path down the tree and never move a node, so they cannot unbalance anything. Each operation is $O (h)$ , and on an AVL tree that is $O (lo g n)$ .