Skip to interview prep
Apexed

184. How does an order-statistic tree support rank and select queries?

HardTrees

Technical
Show model answer

Store in each node the size of its subtree. `select(k)` (the kth smallest) compares k with the left size L: equal to L + 1 returns the node, smaller goes left, larger goes right with k - L - 1. `rank(x)` walks down and, each time it moves right, adds L + 1 for the skipped node and its left subtree.

On a balanced tree (AVL or red-black) both queries are O(log n). Insertions and deletions must update sizes along the path, and every rotation must recompute the sizes of the two rotated nodes, so updates stay O(log n).

How does an order-statistic tree support rank and select queries — Data structures & algorithms interview question — Apexed