Order-Statistic Trees: Rank & Select in O(log n)

1. Introduction & Motivation

A sorted array answers "what is the k-th smallest value?" in $O(1)$ by direct indexing, and "what is this value's rank?" in $O(\log n)$ by binary search. Both answers stop being cheap the moment the data changes: inserting or deleting one element from a sorted array costs $O(n)$, because every element after the insertion point has to shift. An order-statistic tree is a Binary Search Tree (BST) augmented with one extra field per node — the size of the subtree rooted there — so that it answers both queries in $O(\log n)$ and supports $O(\log n)$ insertion and deletion. It gives you the query speed of a sorted array with the mutability of a tree.

Naming collision — read this first: this lesson is completely unrelated to Selection & Order Statistics: Quickselect, Median of Medians, and Top-K, even though both titles contain the phrase "order statistics." That earlier lesson solves a static, one-shot problem — given a fixed array, find its k-th smallest element or a running median — using arrays and heaps (Quickselect, Median-of-Medians, a two-heap streaming median). This lesson solves a dynamic problem — given a data set that is repeatedly inserted into and deleted from, answer rank and select queries at any time — using an augmented Binary Search Tree. The two lessons share a name and a family resemblance (both are about "which element has rank k"), but the underlying data structures, the guarantees they offer, and the situations where you would reach for each one are entirely different. If you came here looking for Quickselect or a running-median heap, that other lesson is the one you want.

Order-statistic trees show up whenever a system needs percentile or ranking information on data that keeps changing: a leaderboard that must report "what rank is this player?" after every match, a monitoring dashboard that tracks a moving median or 95th percentile of live measurements, or a database index that supports both point lookups and "how many rows come before this one" in the same structure. None of these are well served by re-sorting an array on every update.

2. Prerequisites

This lesson builds directly on plain Binary Search Trees. Before continuing, you should be comfortable with:

The BST ordering property: for every node, all values in the left subtree are smaller and all values in the right subtree are larger.
Standard BST search, insert, and delete — including the three deletion cases (leaf, one child, two children via inorder successor). These mechanics are already covered in full, with worked Python/C++/Java code, in DSA Part 10: BST & Balanced Trees — BST Operations. This lesson does not re-derive them; it only adds a size field on top.
Big-O notation and the idea that tree height $h$ determines the cost of a root-to-leaf pass, with $h = O(\log n)$ for a balanced tree and $h = O(n)$ for a degenerate one.
Basic recursion, since every operation below is naturally expressed as a recursive descent that does a small amount of work on the way back up.

3. Core Insight: Subtree-Size Augmentation

                Core insight: storing size[x] — the number of nodes in the subtree rooted at x, including x itself — at every node, and keeping that field correct through every insert and delete, is enough to answer "what is the k-th smallest element?" and "what is this value's rank?" in $O(\log n)$, without ever scanning the data.
            

This is the general pattern behind tree augmentation: attach extra information to each node when two conditions hold. First, the extra information must be locally computable — derivable from a node's own value plus whatever is stored at its immediate children, so it can be recomputed in $O(1)$ after any single-node change. Second, it must be globally sufficient — enough, together with the BST ordering property, to answer the richer query without inspecting nodes outside the search path. Subtree size satisfies both: $$size[x] = size[left(x)] + size[right(x)] + 1$$ and once every ancestor's size is correct, a single root-to-leaf pass can compare a target rank against left-subtree sizes to decide which way to go.

Concretely: at any node x, the number of nodes strictly smaller than x is exactly size(left(x)), because the BST property guarantees the entire left subtree is smaller and the entire right subtree is larger. That single fact is the entire mechanism behind both select and rank below.

4. A Concrete Example

Worked Example

Building the tree and tracing select(5)

Insert 8, 3, 10, 1, 6, 14, 4, 7, 13 into an empty augmented BST, in that order (standard BST insert: smaller goes left, equal-or-larger goes right). The resulting tree, with each node's subtree size in parentheses, is:

                8 (9)
              /        \
          3 (5)         10 (3)
         /     \              \
      1 (1)    6 (3)          14 (2)
              /    \          /
           4 (1)   7 (1)   13 (1)

Sorted order is 1, 3, 4, 6, 7, 8, 10, 13, 14 — nine values, so the 5th smallest should be 7. Trace select(5) using the rule "let r = size(left(x)) + 1 be x's own rank in its subtree; if k == r return x, if k < r recurse left with the same k, otherwise recurse right with k - r":

Step	Current node	left size	r = left size + 1	k	Decision
1	8	5 (subtree at 3)	6	5	5 < 6 → go left, k stays 5
2	3	1 (subtree at 1)	2	5	5 > 2 → go right, k becomes 5-2=3
3	6	1 (subtree at 4)	2	3	3 > 2 → go right, k becomes 3-2=1
4	7	0 (no left child)	1	1	1 == 1 → return 7

Four comparisons found the 5th smallest value in a 9-node tree — no scan, no sort. The same subtree sizes answer a rank query just as cheaply: rank(7) (count of values $\le 7$) walks the same tree and returns 5, confirming that 7 and "5th smallest" are consistent views of the same ordering.

5. Select k-th Smallest

The select(k) operation returns the k-th smallest value (using 1-indexed k, so k = 1 is the minimum). At each node, compare k against r = size(left) + 1, the current node's own rank within its subtree, and recurse accordingly — exactly as traced above. Each implementation below builds the tree with plain BST insertion (kept size-aware) and then runs select for every valid k.

class Node:
    __slots__ = ("value", "left", "right", "size")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.size = 1  # size of the subtree rooted at this node


def size_of(node):
    return node.size if node else 0


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    node.size = 1 + size_of(node.left) + size_of(node.right)
    return node


def select(node, k):
    """Return the k-th smallest value (1-indexed) in the subtree rooted at node."""
    if node is None:
        raise IndexError("k is out of range for this tree")
    left_size = size_of(node.left)
    if k == left_size + 1:
        return node.value
    elif k <= left_size:
        return select(node.left, k)
    else:
        return select(node.right, k - left_size - 1)


root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, value)

for k in range(1, size_of(root) + 1):
    print(f"select({k}) = {select(root, k)}")
# select(1) = 1, select(2) = 3, select(3) = 4, select(4) = 6, select(5) = 7,
# select(6) = 8, select(7) = 10, select(8) = 13, select(9) = 14

#include <iostream>
#include <stdexcept>

struct Node {
    int value;
    Node* left;
    Node* right;
    int size;
    Node(int v) : value(v), left(nullptr), right(nullptr), size(1) {}
};

int sizeOf(Node* node) {
    return node ? node->size : 0;
}

Node* insertNode(Node* node, int value) {
    if (!node) return new Node(value);
    if (value < node->value) node->left = insertNode(node->left, value);
    else node->right = insertNode(node->right, value);
    node->size = 1 + sizeOf(node->left) + sizeOf(node->right);
    return node;
}

int select(Node* node, int k) {
    if (!node) throw std::out_of_range("k is out of range for this tree");
    int leftSize = sizeOf(node->left);
    if (k == leftSize + 1) return node->value;
    if (k <= leftSize) return select(node->left, k);
    return select(node->right, k - leftSize - 1);
}

int main() {
    Node* root = nullptr;
    int values[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
    for (int v : values) root = insertNode(root, v);

    for (int k = 1; k <= sizeOf(root); ++k) {
        std::cout << "select(" << k << ") = " << select(root, k) << '\n';
    }
    // select(1) = 1 ... select(5) = 7 ... select(9) = 14
}

import java.util.NoSuchElementException;

public class OrderStatisticSelect {
    static class Node {
        int value;
        Node left, right;
        int size;
        Node(int value) {
            this.value = value;
            this.size = 1;
        }
    }

    static int sizeOf(Node node) {
        return node == null ? 0 : node.size;
    }

    static Node insert(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value) node.left = insert(node.left, value);
        else node.right = insert(node.right, value);
        node.size = 1 + sizeOf(node.left) + sizeOf(node.right);
        return node;
    }

    static int select(Node node, int k) {
        if (node == null) throw new NoSuchElementException("k is out of range for this tree");
        int leftSize = sizeOf(node.left);
        if (k == leftSize + 1) return node.value;
        if (k <= leftSize) return select(node.left, k);
        return select(node.right, k - leftSize - 1);
    }

    public static void main(String[] args) {
        Node root = null;
        int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        for (int v : values) root = insert(root, v);

        for (int k = 1; k <= sizeOf(root); k++) {
            System.out.println("select(" + k + ") = " + select(root, k));
        }
        // select(1) = 1 ... select(5) = 7 ... select(9) = 14
    }
}

6. Rank Query

The rank(value) operation returns how many stored values are less than or equal to value — the mirror image of select. It works whether or not value is actually present in the tree. Walking down from the root: whenever the current node's value is $\le$ the query value, that node and its entire left subtree (all of it strictly smaller, by the BST property) are all $\le$ value, so add size(left) + 1 to the running count and continue into the right subtree looking for more; whenever the current node's value is $>$ the query value, neither it nor its right subtree can qualify, so move left without adding anything.

class Node:
    __slots__ = ("value", "left", "right", "size")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.size = 1


def size_of(node):
    return node.size if node else 0


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    node.size = 1 + size_of(node.left) + size_of(node.right)
    return node


def rank(node, value):
    """Return the count of stored values that are <= value."""
    count = 0
    while node:
        if node.value <= value:
            count += size_of(node.left) + 1
            node = node.right
        else:
            node = node.left
    return count


root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, value)

print(rank(root, 7))   # 5  -> {1, 3, 4, 6, 7}
print(rank(root, 9))   # 6  -> {1, 3, 4, 6, 7, 8}
print(rank(root, 0))   # 0  -> nothing is <= 0

#include <iostream>

struct Node {
    int value;
    Node* left;
    Node* right;
    int size;
    Node(int v) : value(v), left(nullptr), right(nullptr), size(1) {}
};

int sizeOf(Node* node) { return node ? node->size : 0; }

Node* insertNode(Node* node, int value) {
    if (!node) return new Node(value);
    if (value < node->value) node->left = insertNode(node->left, value);
    else node->right = insertNode(node->right, value);
    node->size = 1 + sizeOf(node->left) + sizeOf(node->right);
    return node;
}

int rankQuery(Node* node, int value) {
    int count = 0;
    while (node) {
        if (node->value <= value) {
            count += sizeOf(node->left) + 1;
            node = node->right;
        } else {
            node = node->left;
        }
    }
    return count;
}

int main() {
    Node* root = nullptr;
    int values[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
    for (int v : values) root = insertNode(root, v);

    std::cout << "rank(7) = " << rankQuery(root, 7) << '\n'; // 5
    std::cout << "rank(9) = " << rankQuery(root, 9) << '\n'; // 6
    std::cout << "rank(0) = " << rankQuery(root, 0) << '\n'; // 0
}

public class OrderStatisticRank {
    static class Node {
        int value;
        Node left, right;
        int size;
        Node(int value) {
            this.value = value;
            this.size = 1;
        }
    }

    static int sizeOf(Node node) { return node == null ? 0 : node.size; }

    static Node insert(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value) node.left = insert(node.left, value);
        else node.right = insert(node.right, value);
        node.size = 1 + sizeOf(node.left) + sizeOf(node.right);
        return node;
    }

    static int rank(Node node, int value) {
        int count = 0;
        while (node != null) {
            if (node.value <= value) {
                count += sizeOf(node.left) + 1;
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Node root = null;
        int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        for (int v : values) root = insert(root, v);

        System.out.println("rank(7) = " + rank(root, 7)); // 5
        System.out.println("rank(9) = " + rank(root, 9)); // 6
        System.out.println("rank(0) = " + rank(root, 0)); // 0
    }
}

7. Insert/Delete with Size Maintenance

Insertion and deletion follow the standard BST algorithms from DSA Part 10 exactly — this lesson does not change the tree shape logic at all. The only addition is a post-recursion step: after each recursive call returns, recompute the current node's size from its (possibly new) children, the same "recompute on the way back up" pattern used for AVL node heights. Because this recomputation is unconditional, it is correct whether a node was actually added/removed below or not, so it needs no special-casing.

class Node:
    __slots__ = ("value", "left", "right", "size")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.size = 1


def size_of(node):
    return node.size if node else 0


def update_size(node):
    if node:
        node.size = 1 + size_of(node.left) + size_of(node.right)


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    update_size(node)
    return node


def find_min(node):
    while node.left:
        node = node.left
    return node


def delete(node, key):
    if node is None:
        return None
    if key < node.value:
        node.left = delete(node.left, key)
    elif key > node.value:
        node.right = delete(node.right, key)
    else:
        # Same three cases as plain BST delete: leaf, one child, two children.
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = find_min(node.right)
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    update_size(node)
    return node


def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)


root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, value)

out = []
inorder(root, out)
print("Before delete:", out, "size:", size_of(root))  # size: 9

root = delete(root, 6)  # two-children case: successor is 7
out = []
inorder(root, out)
print("After delete(6):", out, "size:", size_of(root))  # size: 8

#include <iostream>
#include <vector>

struct Node {
    int value;
    Node* left;
    Node* right;
    int size;
    Node(int v) : value(v), left(nullptr), right(nullptr), size(1) {}
};

int sizeOf(Node* node) { return node ? node->size : 0; }

void updateSize(Node* node) {
    if (node) node->size = 1 + sizeOf(node->left) + sizeOf(node->right);
}

Node* insertNode(Node* node, int value) {
    if (!node) return new Node(value);
    if (value < node->value) node->left = insertNode(node->left, value);
    else node->right = insertNode(node->right, value);
    updateSize(node);
    return node;
}

Node* findMin(Node* node) {
    while (node->left) node = node->left;
    return node;
}

Node* deleteNode(Node* node, int key) {
    if (!node) return nullptr;
    if (key < node->value) {
        node->left = deleteNode(node->left, key);
    } else if (key > node->value) {
        node->right = deleteNode(node->right, key);
    } else {
        if (!node->left) return node->right;
        if (!node->right) return node->left;
        Node* successor = findMin(node->right);
        node->value = successor->value;
        node->right = deleteNode(node->right, successor->value);
    }
    updateSize(node);
    return node;
}

void inorder(Node* node, std::vector<int>& out) {
    if (node) {
        inorder(node->left, out);
        out.push_back(node->value);
        inorder(node->right, out);
    }
}

int main() {
    Node* root = nullptr;
    int values[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
    for (int v : values) root = insertNode(root, v);

    std::cout << "size before delete: " << sizeOf(root) << '\n'; // 9

    root = deleteNode(root, 6);
    std::vector<int> after;
    inorder(root, after);
    std::cout << "size after delete(6): " << sizeOf(root) << '\n'; // 8
    for (int v : after) std::cout << v << ' ';
    std::cout << '\n'; // 1 3 4 7 8 10 13 14
}

import java.util.ArrayList;
import java.util.List;

public class OrderStatisticMaintenance {
    static class Node {
        int value;
        Node left, right;
        int size;
        Node(int value) {
            this.value = value;
            this.size = 1;
        }
    }

    static int sizeOf(Node node) { return node == null ? 0 : node.size; }

    static void updateSize(Node node) {
        if (node != null) node.size = 1 + sizeOf(node.left) + sizeOf(node.right);
    }

    static Node insert(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value) node.left = insert(node.left, value);
        else node.right = insert(node.right, value);
        updateSize(node);
        return node;
    }

    static Node findMin(Node node) {
        while (node.left != null) node = node.left;
        return node;
    }

    static Node delete(Node node, int key) {
        if (node == null) return null;
        if (key < node.value) {
            node.left = delete(node.left, key);
        } else if (key > node.value) {
            node.right = delete(node.right, key);
        } else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;
            Node successor = findMin(node.right);
            node.value = successor.value;
            node.right = delete(node.right, successor.value);
        }
        updateSize(node);
        return node;
    }

    static void inorder(Node node, List<Integer> out) {
        if (node != null) {
            inorder(node.left, out);
            out.add(node.value);
            inorder(node.right, out);
        }
    }

    public static void main(String[] args) {
        Node root = null;
        int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        for (int v : values) root = insert(root, v);

        System.out.println("size before delete: " + sizeOf(root)); // 9

        root = delete(root, 6);
        List<Integer> after = new ArrayList<>();
        inorder(root, after);
        System.out.println("size after delete(6): " + sizeOf(root)); // 8
        System.out.println(after); // [1, 3, 4, 7, 8, 10, 13, 14]
    }
}

One caveat worth a single sentence: if you layer this augmentation onto a self-balancing tree (AVL or Red-Black, covered in DSA Part 10's rotation section), every rotation must also recompute the size of the nodes it moves, in addition to whatever height or color bookkeeping the balancing scheme already does — the rotation logic itself is unchanged and is not re-derived here.

Dynamic Order Statistics

Put together, select, rank, insert, and delete give a single structure that answers both order-statistic queries while the data set is changing. A sorted array can answer the same two queries when the data is static, but every insertion or deletion costs $O(n)$ because elements must shift to keep the array sorted. The augmented BST pays $O(\log n)$ for every one of the four operations (on a balanced tree), which is what makes it the right choice for data that is queried and mutated in the same session rather than sorted once and read many times.

8. Complexity Analysis

                Time: $O(h)$ for select, rank, insert, and delete, where $h$ is the tree's height. On a balanced tree, $h = O(\log n)$, so all four operations run in $O(\log n)$. On a degenerate tree built from already-sorted input, $h = O(n)$, so every operation degrades to $O(n)$ — no better than a plain unbalanced BST, because the size field adds only $O(1)$ work per node and cannot fix a skewed shape. Space: $O(1)$ extra per node for the size field, $O(n)$ total, plus $O(h)$ recursion stack.
            

The size field never improves worst-case height on its own — it rides on top of whatever shape the tree already has. In production, this augmentation is combined with a self-balancing scheme, most commonly AVL or Red-Black trees (see DSA Part 10: BST & Balanced Trees), so that $h = O(\log n)$ is guaranteed rather than merely typical.

9. Applications & Alternatives

Where order-statistic trees show up

Live leaderboards: report a player's current rank immediately after any score changes, without re-sorting the whole leaderboard.
Rolling percentiles: track a moving median or 95th-percentile latency over a sliding window of measurements that are both added and expired.
Database indexes: some index structures support "how many rows precede this key" alongside ordinary point and range lookups by keeping a count at each internal node.
Competitive programming: "count elements less than X" and "find the k-th element" under interleaved updates are common building blocks in problems that forbid re-sorting after every operation.

A Fenwick Tree (Binary Indexed Tree) offers a different route to the same rank/select functionality when values can be mapped to a small range of indices up front — it trades the flexibility of arbitrary insertion order for a simpler, array-backed implementation. That alternative, including a full point-update/prefix-query implementation, is covered in Union-Find, Trie, Fenwick Tree & Segment Tree — Fenwick Tree; it is not re-derived here.

10. Exercises

Easy

Given an order-statistic tree of $n$ values, find the median using select. Handle both odd $n$ (a single middle element) and even $n$ (the average of the two middle elements).

Medium

Implement Kth Largest Element in a Stream (LeetCode 703) using an order-statistic tree instead of a fixed-size min-heap: insert each new value and use select to read off the k-th largest at any point. Compare the tradeoffs against the heap solution — the tree costs more per operation for a fixed k but also supports arbitrary rank/select queries and value removal, which a size-bounded heap does not.

Hard

Solve Count of Smaller Numbers After Self (LeetCode 315) by processing the array from right to left: for each element, query rank (adjusted for strictly-less-than) against the values inserted so far, then insert the current element. An alternative approach — mapping values to dense ranks with coordinate compression and pairing them with a Fenwick Tree — is developed in Prefix Sums, Difference Arrays & Coordinate Compression — Coordinate Compression; that derivation is not repeated here.

Mastery challenge: Design a live-leaderboard service that supports inserting a new score, updating an existing player's score, and answering "what is this player's current rank?" and "who holds rank k?" at any time, all under $O(\log n)$. State which augmentation you need beyond subtree size (if any), how you would balance the tree, and what changes if scores are not unique.

Review rhythm: tomorrow, redo the select(5) hand-trace from Section 4 without looking at the table; next week, implement select, rank, insert, and delete from a blank file in all three languages; several weeks later, work the Kth Largest Element in a Stream problem again and compare your order-statistic-tree solution against a heap-based one from memory. Finally, explain to someone who only knows plain BSTs why a size field is enough to answer rank and select in $O(\log n)$.

11. Summary Cheat Sheet

An order-statistic tree is a BST plus one field per node: size, the count of nodes in its subtree (including itself).
It is unrelated to Quickselect/Median-of-Medians/streaming-median "order statistics" covered in the array/heap-based sibling lesson — same name, different structure, different guarantees.
size[x] = size[left(x)] + size[right(x)] + 1, recomputed in $O(1)$ after any single-node change.
select(k): compare k against size(left) + 1 at each node to decide left, return, or right-with-adjusted-k.
rank(value): count size(left) + 1 whenever the current node is $\le$ value, then continue right; otherwise go left without counting.
Insert and delete reuse plain BST logic unchanged; only a post-recursion size recompute is added.
Balanced height gives $O(\log n)$ for all four operations; an unbalanced tree degrades to $O(n)$, which is why production systems pair this augmentation with AVL or Red-Black balancing.
A Fenwick Tree over coordinate-compressed values is a common array-based alternative when insertion order doesn't need to be arbitrary.

Cookie Consent

Order-Statistic Trees: Rank & Select in O(log n)

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Core Insight: Subtree-Size Augmentation

4. A Concrete Example

Building the tree and tracing select(5)

5. Select k-th Smallest

6. Rank Query

7. Insert/Delete with Size Maintenance

Dynamic Order Statistics

8. Complexity Analysis

9. Applications & Alternatives

Where order-statistic trees show up

10. Exercises

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Order-Statistic Trees: Rank & Select in O(log n)

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Core Insight: Subtree-Size Augmentation

4. A Concrete Example

Building the tree and tracing select(5)

5. Select k-th Smallest

6. Rank Query

7. Insert/Delete with Size Maintenance

Dynamic Order Statistics

8. Complexity Analysis

9. Applications & Alternatives

Where order-statistic trees show up

10. Exercises

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 10: BST & Balanced Trees

Selection & Order Statistics: Quickselect Guide