Solution: rank

rank searches for the key, and on the way down it counts the keys it passes that are smaller. At a node, there are three cases:

If key is smaller than the node’s key, every smaller key in this subtree is in the left subtree. The rank is the rank in the left subtree.
If key is larger, the whole left subtree and the node itself are smaller than key. That is size(node.left) + 1 keys, plus the rank in the right subtree.
If key equals the node’s key, the smaller keys are exactly the left subtree.

Reaching a null child means there is nothing more to count.

@Override
public int rank(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  return rank(root, key);
}

// Returns the number of keys smaller than key in the subtree rooted at node.
private int rank(Node<K, V> node, K key) {
  if (node == null) {
    return 0;
  }

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

The key does not have to be in the map. If it is missing, the search ends at null, which returns $0$ . By then the sum already includes every smaller key the search passed on the way down.

Tracing rank(72)

At the root 50: $72 > 50$ , so 50 and its left subtree of size $3$ are smaller. That is $4$ so far, and we go right. At 70: $72 > 70$ , so 70 and its left subtree of size $1$ add $2$ , for $6$ , and we go right. At 80: $72 < 80$ , so we go left without counting. At 75: $72 < 75$ , so we go left again and reach null. The visited nodes are filled:

                 ╭──────╮
                 │█50:9█│
                 ╰───┬──╯
         ┌───────────┴───────────┐
     ╭───┴──╮                ╭───┴──╮
     │ 30:3 │                │█70:5█│
     ╰───┬──╯                ╰───┬──╯
    ┌────┴────┐          ┌───────┴───────┐
╭───┴──╮  ╭───┴──╮   ╭───┴──╮        ╭───┴──╮
│ 20:1 │  │ 40:1 │   │ 60:1 │        │█80:3█│
╰──────╯  ╰──────╯   ╰──────╯        ╰───┬──╯
                                    ┌────┴────┐
                                ╭───┴──╮  ╭───┴──╮
                                │█75:1█│  │ 90:1 │
                                ╰──────╯  ╰──────╯

rank(72) returns $6$ : the keys 20, 30, 40, 50, 60, and 70.

Cost

Like select, rank is $O (h)$ , which is $O (lo g n)$ on an AVL tree.

The two queries are inverses. For a stored key, select(rank(key) + 1) is that key, and for every k from $1$ to size(), rank(select(k)) is k - 1.