Order Statistics and Codec

What is this?

A BST already knows the order of its values, so it can answer position questions — what comes next, how many are smaller — and it can even save itself to a flat list and rebuild perfectly. You lean on the sorted shape instead of storing extra bookkeeping. The order rule alone carries enough information to reconstruct the whole tree.

💡 Fun fact: Serializing a general binary tree needs null markers to record its shape, but a BST does not. Just write the values in preorder — the ordering rule alone tells you exactly where each value belongs when you rebuild.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Because a BST already encodes a total order, it can answer positional and counting questions — what comes next, how many are smaller — and even rebuild itself from a flat list without storing any structure markers. The shared thread is that the ordering invariant is enough information; you never need to record shape explicitly, only the values and the rule that arranges them.

The pattern

These problems lean on the same fact from two directions. The inorder sequence of a BST is sorted, so "the next value" or "how many are smaller" become questions about position in that sequence rather than full traversals. And because the sorted order is recoverable from comparisons alone, a preorder list plus the bounds rule is enough to reconstruct the exact tree — no null markers, no delimiters beyond the values themselves.

So you either navigate the order (successor, rank) in O(h) or O(log n) per query, or you exploit the order to rebuild the whole tree in a single O(n) pass. Either way the win is the same: the invariant carries the structure for you.

The problems

• Inorder Successor in BST — find the next-largest key in O(h) without a full traversal. If the node has a right subtree, the successor is its leftmost descendant; otherwise it is the lowest ancestor for which the node sits in the left subtree. A single downward walk finds it.
• Count of Smaller Numbers After Self — for each element, count how many later elements are smaller. Solvable with an order-statistics BST (augment nodes with subtree sizes), a Binary Indexed Tree over compressed values, or merge sort that counts inversions while merging. All three turn the rank query into roughly O(n log n).
• Serialize and Deserialize BST — flatten and rebuild, marker-free. Emit keys in preorder, then on the way back reconstruct using the bounds rule: each value claims the next position that fits its (low, high) window. The BST invariant replaces the null sentinels a general binary tree would require, making the encoding compact.

Key takeaways

• A BST is a sorted sequence in disguise — successor and rank are position questions, not full scans.
• Inorder successor is O(h): leftmost of the right subtree, or the lowest left-turning ancestor.
• Counting smaller-after has three idiomatic tools — order-statistics BST, BIT over compressed values, or merge-sort inversion counting — each about O(n log n).
• BST serialization needs no markers: preorder plus the bounds rule reconstructs the exact tree.
• The bounds rule does the rebuilding — each value takes the first slot whose (low, high) window admits it.
• Order replaces structure: because comparisons recover shape, you store values, not topology.

Order: Inorder Successor in BST → Count of Smaller Numbers After Self → Serialize and Deserialize BST.