The QuickSort–BST Bijection & Indicator Random Variables
Let $z_1 < z_2 < \dots < z_N$ denote the $N$ keys in sorted order, and suppose we insert them into an initially empty BST according to a uniformly random permutation $\pi$. In the resulting tree $T$, the depth $d(z_i)$ of node $z_i$ equals the number of strict ancestors of $z_i$. Using Linearity of Expectation and indicator random variables
$$X_{ij} = \mathbb{I}\{\text{node } z_i \text{ is an ancestor of node } z_j\}$$
we can express the depth of $z_j$ as $d(z_j) = \sum_{i \ne j} X_{ij}$, and the Total Internal Path Length $D(T) = \sum_{j=1}^N d(z_j)$ as:
$$\mathbb{E}[D(T)] = \sum_{j=1}^N \sum_{i \ne j} \Pr[z_i \text{ is an ancestor of } z_j]$$
| Metric on $N$-Node BST | Uniformly Random Permutation $\pi \in S_N$ | Uniformly Random Tree Topology (Catalan $C_N$) | Adversarial Sorted Input |
|---|---|---|---|
| Expected Node Depth $\mathbb{E}[d(x)]$ | 2 ln N ≈ 1.386 log₂ N | Θ(√N) | (N - 1) / 2 |
| Expected Tree Height $\mathbb{E}[h(T)]$ | ≈ 4.311 ln N ≈ 2.988 log₂ N | √(π N) | N - 1 |
| Probability of Balanced Split ($1/4 \le k/N \le 3/4$) | p = 1/2 per level | Exponentially small | p = 0 |
Theorem: Ancestor Probability $\Pr[X_{ij} = 1] = \frac{2}{|j - i| + 1}$ & Reed's Height Constant
Consider the contiguous sorted subarray of keys $Z_{ij} = \{z_{\min(i,j)}, \dots, z_{\max(i,j)}\}$, which contains $|j - i| + 1$ elements. Look at the very first element $z_k \in Z_{ij}$ to be inserted under permutation $\pi$:
- If $z_k = z_i$ executes first, $z_i$ becomes the root of the subtree containing $z_j$, so $z_i$ is an ancestor of $z_j$.
- If $z_k$ is strictly between $z_i$ and $z_j$ ($\min(i,j) < k < \max(i,j)$), then $z_k$ separates $z_i$ and $z_j$ into its left and right subtrees, making it impossible for $z_i$ to ever be an ancestor of $z_j$!
- If $z_k = z_j$ executes first, $z_j$ is an ancestor of $z_i$, so $z_i$ is not an ancestor of $z_j$.
Since $\pi$ is uniformly random, each of the $|j - i| + 1$ elements in $Z_{ij}$ is equally likely to appear first. Therefore, $\Pr[z_i \text{ is an ancestor of } z_j] = \frac{1}{|j - i| + 1}$, and summing over all pairs yields:
$$\mathbb{E}[D(T)] = 2 \sum_{i=1}^N \sum_{j=i+1}^N \frac{1}{j - i + 1} = 2N H_N - 4N + 2N = 2(N + 1)H_N - 4N \approx (2 \ln 2) N \log_2 N \approx 1.386 N \log_2 N$$
Furthermore, using Jensen's Inequality on the exponential potential $\mathbb{E}[3^{h(T)}]$ (CLRS §12.4) bounds $\mathbb{E}[h(T)] \le 3 \log_{4/3} N$, and Bruce Reed (2003) proved the exact asymptotic expansion $\mathbb{E}[h(T)] = \alpha \ln N - \beta \ln \ln N + O(1)$ where $\alpha \approx 4.31107$ satisfies $\alpha \ln(2e/\alpha) = 1$.
Step through Hibbard’s 3-case BST deletion (splicing out the in-order successor y = min(z.right) when deleting a 2-child node z), or inspect the exact bijection between Random BST depth and QuickSort pivot comparisons.
Invariant & State
Visualizing the QuickSort Pivot ↔ BST Ancestor Isomorphism
Hardware Reality: Why $1.386 \log_2 N$ Beats Rotation-Heavy Trees on Static Read-Mostly Workloads
A strictly balanced AVL tree has worst-case height $\le 1.44 \log_2 N$ and average depth $\approx 1.04 \log_2 N$, whereas a Randomly Built BST has average depth $\approx 1.386 \log_2 N$—only 34% more comparisons on average, while requiring zero balance-factor metadata bytes and zero pointer-modifying rotations! When building a BST offline from a known dataset, shuffling the input array with Fisher-Yates (or assigning random heap priorities as in a Treap, Module 08) guarantees $O(\log N)$ expected height against any adversarial input order.
Implementation: Monte Carlo Verification of Ancestor Harmonic Law & Fisher-Yates Pre-Shuffle
// C++20: Offline Randomized BST Builder via Fisher-Yates Shuffle + Exact Harmonic Depth Estimator
#include <vector>
#include <random>
#include <cmath>
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
explicit Node(int k) : key(k) {}
};
void insertBST(Node*& root, int key) {
Node** curr = &root;
while (*curr != nullptr) {
curr = (key < (*curr)->key) ? &((*curr)->left) : &((*curr)->right);
}
*curr = new Node(key);
}
// Eliminates O(N) sorted-input degeneration before bulk BST insertion
Node* buildRandomBST(std::vector<int> keys, uint64_t seed = 42) {
std::mt19937_64 rng(seed);
for (size_t i = keys.size(); i > 1; --i) {
std::uniform_int_distribution<size_t> dist(0, i - 1);
std::swap(keys[i - 1], keys[dist(rng)]);
}
Node* root = nullptr;
for (int k : keys) insertBST(root, k);
return root;
}
// Exact theoretical expected depth of a random node in an N-node Randomly Built BST
double expectedRandomBSTDepth(int n) {
double harmonic = 0.0;
for (int k = 1; k <= n; ++k) harmonic += 1.0 / k;
return (2.0 * (n + 1) / n) * harmonic - 4.0;
}Failure Modes & Adversarial Pitfalls
- Confusing "Randomly Built BST" with "Uniformly Random Binary Tree": There are $N!$ permutations in $S_N$ but only $C_N = \frac{1}{N+1}\binom{2N}{N}$ distinct BST topologies. The mapping from permutations to trees is heavily non-uniform: for $N=3$, both permutations $(2, 1, 3)$ and $(2, 3, 1)$ build the balanced tree rooted at $2$ (probability $2/6 = 1/3$), whereas each of the four height-2 chains is built by only $1/6$ of permutations! If you sample a tree uniformly from the $C_N$ Catalan topologies instead of inserting a random permutation, the expected height explodes from $\Theta(\log N)$ to $\Theta(\sqrt{N})$!
- Online Adversaries Without Randomization: A Randomly Built BST assumes the input permutation is random. In an online server accepting network requests, an attacker can send sorted keys to force $O(N)$ height unless the data structure itself randomizes inside
insert(which is exactly what a Randomized Treap or Skip List does).