Difficulty: Intermediate-Hard | Prerequisites: Binary search trees, expected value, indicator random variables, harmonic series, Quicksort analysis.
Random binary search trees connect data-structure analysis to sorting theory. The key insight is that the random construction process mirrors Quicksort: the root acts as a pivot, and the left and right subtrees correspond to the two recursive sub-problems. This means the expected depth of any node in a random BST is the same as the expected number of comparisons involving that element during Quicksort, which is O(log n). If you understand the Quicksort analysis, you already have the tools for this proof.
A random BST on {1, ..., n} is built by choosing a random root and recursing. The expected depth of any node is O(log n), proved by the same indicator-variable argument used for Quicksort's expected comparisons. Searching in a random BST takes O(log n) expected time.
Binary search tree (BST)
A binary tree where every node's left descendants have smaller values and every node's right descendants have larger values. In simple terms, it is a tree that keeps things in sorted order so you can search by going left or right.
Random BST
A BST built by choosing the root uniformly at random from the available values, then recursing on the left and right ranges. Think of it as inserting elements in a uniformly random permutation order.
Depth of a node
The number of edges on the path from the root to that node. Depth determines search time: finding a node at depth d requires d + 1 comparisons.
Ancestor
In the context of this proof, node j is an ancestor of node i if j lies on the path from the root to i. The depth of i equals the number of its proper ancestors.
Given integers l, ..., r, pick x uniformly from {l, ..., r} as the root.
If l < x, recursively build a random BST on l, ..., x-1 for the left subtree.
If x < r, recursively build a random BST on x+1, ..., r for the right subtree.
Base case: if l = r, the tree is a single node.
The random BST construction on {1, ..., n} produces exactly the same tree as inserting elements in a uniformly random permutation into an initially empty BST. The root corresponds to Quicksort's first pivot, the left subtree to the recursive sort of elements less than the pivot, and the right subtree to the recursive sort of elements greater than the pivot.
Fix a target value i ∈ {1, ..., n}. We want to show E[depth(i)] = O(log n).
The depth of node i equals the number of its ancestors (nodes on the root-to-i path, excluding i itself). Define indicator random variables:
For each j ≠ i, let X_j = 1 if j is an ancestor of i, and X_j = 0 otherwise.
Then depth(i) = Σ_{j≠i} X_j, and by linearity of expectation, E[depth(i)] = Σ_{j≠i} Pr[j is an ancestor of i].
Consider the values between i and j (inclusive). Node j is an ancestor of i if and only if j is the first among {min(i,j), min(i,j)+1, ..., max(i,j)} to be chosen as a root/pivot at some level of the recursion.
This is exactly the same condition as in Quicksort: j is compared with i if and only if j is the first element chosen from the set {min(i,j), ..., max(i,j)}. Since each element in this set is equally likely to be chosen first:
Pr[j is an ancestor of i] = 1 / |i - j| + 1
(when i < j, the set has j - i + 1 elements; symmetrically for j < i.)
E[depth(i)] = Σ_{j≠i} 1/(|i - j| + 1)
Splitting into j < i and j > i:
E[depth(i)] = Σ_{k=1}^{i-1} 1/(k+1) + Σ_{k=1}^{n-i} 1/(k+1)
Each sum is at most Σ_{k=1}^{n-1} 1/(k+1) ≤ Σ_{m=2}^{n} 1/m ≤ ln(n).
So E[depth(i)] ≤ 2 ln(n) = O(log n).
Since this holds for every i, the expected depth of any particular node is O(log n), and therefore searching for any value takes O(log n) expected time.
⚠️ The proof relies on linearity of expectation over indicator random variables. Know this technique cold.
⚠️ Students often confuse expected depth O(log n) with a guarantee that the tree is balanced. It is not: individual trees can be very unbalanced, but on average they are not.
⚠️ The Quicksort analogy is the key insight the exam will test. Be able to articulate precisely: "j is an ancestor of i iff j is the first element chosen from {min(i,j), ..., max(i,j)}."
⚠️ Students sometimes bound the sum incorrectly. The harmonic sum H_n = 1 + 1/2 + ... + 1/n = O(log n) is the fact you need.
⚠️ The result is about expected depth of a fixed node over the randomness of the tree construction, not about average depth across all nodes (though both are O(log n)).
Q: What is the expected depth of node 1 in a random BST on {1, ..., n}?
A: E[depth(1)] = Σ_{j=2}^{n} 1/j = H_n - 1 = O(log n). Node 1 has no elements to its left, so only the rightward sum contributes.
Q: Why is the random BST construction equivalent to inserting elements in a random permutation?
A: Choosing the root uniformly and recursing is the same as: the first element inserted becomes the root, smaller elements go left, larger go right. A uniformly random choice at each level is equivalent to a uniformly random insertion order.
Q: State the indicator variable used in the proof and its probability.
A: X_j = 1 if j is an ancestor of i. Pr[X_j = 1] = 1/(|i - j| + 1), because j must be the first chosen among the |i - j| + 1 elements between i and j inclusive.
Q: True or False: The expected depth of the node with value n/2 is smaller than the expected depth of the node with value 1.
A: False. Both are O(log n). The node with value 1 has E[depth] = H_n - 1, while the middle node has E[depth] ≤ 2 ln(n). The constants differ, but both are Θ(log n).
This result connects directly to the Quicksort analysis from earlier in the course: both use the same indicator-variable decomposition and harmonic-sum bound. It also relates to balanced BSTs (AVL, red-black trees), which enforce O(log n) depth deterministically, at the cost of maintaining balance invariants. The probabilistic analysis here shows that randomisation alone achieves the same expected performance without any rebalancing.
Random binary search tree, expected depth, Quicksort analogy, indicator random variable, linearity of expectation, harmonic number, harmonic series, ancestor, BST search time, balanced BST, AVL tree, random permutation, EECS 376