A binary search tree can locate a key by comparison, but the ordinary ordering invariant does not directly tell us how many keys lie below a node. Store one extra number per node and a search can instead answer: which key is the fifth smallest? The extra number is useful only if every update preserves its meaning.
1. Define the augmentation
Definition 4.1.1
(Subtree size and rank)
Assume a finite binary search tree of distinct keys, where every key in a left subtree is smaller than the node's key and every key in its right subtree is larger. Each node stores the number of nodes in its entire subtree, including itself. For an empty subtree write . The local rule is
The rank of a key in the tree is plus the number of keys smaller than ; the th smallest key is the key of rank .
We count rank starting at 1. The operation below requires ; reject an out-of-range rank before searching. In particular, the empty tree has no valid rank. Distinctness makes “the th smallest key” unambiguous. Supporting duplicates needs an explicit multiplicity convention and different counts; it is not silently covered here.
2. Selection algorithm
At a current node, let be the stored size of its left subtree. Exactly keys precede the current key within that subtree, so its local rank is .
select(root, k): // precondition: 1 <= k <= size(root)
x = root
while x is not empty:
L = size(x.left)
if k == L + 1: return x.key
if k <= L:
x = x.left
else:
k = k - (L + 1)
x = x.right
Theorem 4.1.2
(Correctness and cost of rank selection)
Let be a binary search tree of distinct keys whose stored sizes satisfy the local rule, and let . Then select(root, k) returns the th smallest key of . If is the height in edges, it examines at most nodes.
Proof
(A loop invariant on the current rank)
Claim: at every loop entry, x is nonempty, , and the key to return is the th smallest key of the subtree rooted at x. At the first entry this is the caller's request, by the precondition.
Suppose the claim holds at an entry, and let . By the ordering, the subtree's keys appear in the order: the keys of the left subtree, then the key of x, then the keys of the right subtree. If , the answer is the key of x, and it is returned. If , then , so the left child is nonempty, , and the th smallest key of the subtree is the th smallest key of the left subtree. If , then and ; so the right child is nonempty and the answer is its th smallest key. In both descents the claim holds at the next entry with a child of x. Each step moves down one level, so the loop makes at most entries, and since x stays nonempty it can end only by the return.
Proof X-ray
Why the loop never leaves the tree
Two facts carry the argument. First, the ordering of a binary search tree makes the ranks inside a subtree fall into three consecutive blocks, left keys, the node, right keys, so a rank can be translated into a rank in one child. Second, the stored size appears in the proof twice: locates the blocks, and shows that the translated rank still lies in range. If one stored size were stale, the second inequality could fail and the descent could reach an empty child. Distinctness is also used: with repeated keys the phrase "the th smallest key" would not single out one node.
If height counts edges on a longest root-to-leaf path, at most nodes are examined. Selection therefore costs time and extra space; the size fields use storage across nodes. An unbalanced tree can have , so logarithmic time requires an additional balance guarantee.
Counterexample mode
Running select without checking the rank
Claim: the loop returns a key whatever is. Take the seven-node tree of the next section and . At 16 we have and , so becomes and becomes 24. At 24, and , so becomes and becomes 31. At 31, and , so becomes and becomes the empty right child; the loop ends without any return. For the path 16, 7, 3 ends the same way, in the empty left child of 3. The repair is the stated precondition: reject every with or before the search starts.
3. Work a small tree
Use the following distinct-key tree, where the number in parentheses is the stored subtree size:
16(7)
/ \
7(3) 24(3)
/ \ / \
3(1) 11(1) 20(1) 31(1)
Worked example 4.1.3
(Rank 5 in a seven-node tree)
Find rank . At 16, the left size is 3, so skip its three keys and 16; the right subtree is searched for rank . At 24, the left size is 1, so descend left without changing that rank. At 20, the left size is 0 and , so return 20. The inorder sequence is 3, 7, 11, 16, 20, 24, 31, which independently checks the result.
Worked example 4.1.4
(The smallest key, the largest key and the root)
For : at 16 the left size is 3 and , so go left; at 7 the left size is 1 and , so go left; at 3 the left size is 0 and , so return 3, the smallest key. For : at 16, , so becomes and we go right; at 24, , so becomes and we go right; at 31, , so return 31, the largest. For the root answers at once, because ; the inorder list agrees that the fourth key is 16.
4. Keep sizes correct when the tree changes
After inserting a new distinct key as a leaf, set its size to 1 and recompute the stored size on each ancestor along the search path, from the bottom upward. If a duplicate insertion is rejected, the tree and its counts remain unchanged. Deletion must similarly recompute every ancestor affected by the physical removal. In particular, for a two-child deletion implemented by copying the inorder successor's key and then removing the successor node, recompute upward from the removed node's former parent, including the target node when applicable. The case where the successor is the target's immediate right child is included; the target itself is then that former parent. These are update rules for a single operation, not a license to expose the transient key-copy state to concurrent readers.
A rotation preserves the inorder key sequence but changes which nodes belong to two local subtrees. After a left rotation of x with right child y, recompute s(x) first and then s(y) from their new children. Higher ancestors retain the same set of descendants under this local rotation. A balancing algorithm can use these local updates, but this lesson does not prove any balancing algorithm or promise logarithmic height.
Worked example 4.1.5
(Sizes after a left rotation at the root)
In the seven-node tree, rotate left at x = 16 with right child y = 24. Then 24 becomes the root, 16 its left child, and the former left child 20 of 24 becomes the right child of 16; the left child 7(3) of 16 is unchanged. Recompute s(16)=1+3+1=5 first, then s(24)=1+5+1=7. The inorder sequence is still 3, 7, 11, 16, 20, 24, 31. Selecting rank 5 now: at 24, and , go left; at 16, and , so becomes and we go right; at 20, , return 20, as before.
Common mistake
(Skipping only the left keys when going right)
When , the keys skipped are the left keys and the current key, so the new rank is . Subtracting only gives a rank that is too large by one. In the seven-node tree with , the root would send us right with rank ; at 24 we have and , so the code would return 24. The correct answer is 20.
Common mistake
(Recomputing sizes in the wrong order after a rotation)
After the left rotation above, 16 is the lower node and 24 the upper one. The size of 24 depends on the new size of 16. If s(24) is recomputed first, it uses the stale value and gives instead of . Recompute the lower node first, then the upper one.
5. Checks and exercises
Quick check
(Insert 18 in the worked tree and update all affected sizes. What does rank 6 return afterwards?)
Follow the search path for 18 and recompute from the bottom up.
Solution · Answer
The path is 16 -> 24 -> 20; 18 becomes the left child of 20. The updated sizes at 20, 24, and 16 are 2, 4, and 8. Selecting rank 6 now returns 20, since the inorder sequence is 3, 7, 11, 16, 18, 20, 24, 31.
Quick check
(What should a rank of 0 or 8 mean in the original seven-node tree?)
Compare with the precondition of select.
Solution · Answer
Neither is valid under the 1-based contract; reject it rather than returning a sentinel that might be mistaken for a key.
Quick check
(Why is the ordinary BST ordering invariant alone insufficient for the stated complexity?)
Ask what the algorithm must know at each node.
Solution · Answer
Without stored sizes, finding may require counting a large subtree. With sizes, each level's rank decision is constant work in the usual pointer model.
Quick check
(Explain why the same key set can have different heights in different BSTs.)
Think of the order in which the keys are inserted.
Solution · Answer
Inserting sorted distinct keys into a plain, unbalanced BST can form a chain; correct rank selection still works, but may visit linearly many nodes.
The local invariant and cost analysis assume correctly initialized counts and no concurrent mutation during the operation.