Wait, What?
To generate a uniformly random binary-tree shape, Rémy’s algorithm does not calculate Catalan probabilities at every branch. It grows the tree by a reversible random graft.
Rémy’s algorithm is an elegant exact sampler for full ordered binary trees of a prescribed size. Start with one leaf. Repeatedly choose one existing node uniformly, insert a new internal node above it, add one new leaf as the other child, and flip a fair coin to decide left-versus-right orientation. After n growth steps, the result is a full binary tree with n internal nodes and n+1 leaves. The remarkable part is not merely that the algorithm is fast. It produces each Catalan tree shape with exactly the same probability.
Quick Answer
Learn Rémy through full binary trees → Catalan counting → decorated leaves → random grafting → reversible deletion → uniformity proof → O(n) implementation → random-bit cost → statistical validation → extensions and comparison with other samplers. The key proof technique is a bijection: every decorated tree of size n has exactly one predecessor when the newest leaf is removed.
1. Be Precise About the Object Being Sampled
A full binary tree is a rooted binary tree in which every internal node has exactly two children. In the ordered or plane version, left and right children are distinct. A tree with n internal nodes has n+1 leaves and 2n+1 total nodes.
The number of ordered full binary-tree shapes with n internal nodes is the nth Catalan number:
C_n = (1/(n+1)) * binomial(2n, n)A uniform sampler must give every one of those C_n shapes probability exactly 1/C_n.
2. Why Naive Recursive Sampling Is More Subtle Than It Looks
Because Catalan numbers satisfy C_n=Σ C_i C_(n-1-i), it is tempting to choose a left-subtree size uniformly from 0…n-1 and recurse. That is not uniform over tree shapes. Different split sizes correspond to different numbers of possible left/right shape pairs.
A correct Catalan recursive sampler must weight each split i proportionally to C_i C_(n-1-i). Rémy’s algorithm avoids repeatedly evaluating those split probabilities by using an incremental bijection instead.
3. The Growth Step
Start with a single leaf labelled 0. For i=1,2,…,n:
- Choose uniformly one existing node x. Equivalently, choose the subtree rooted at x.
- Create a new internal node p where x used to attach to its parent. If x was the root, p becomes the new root.
- Create a new leaf labelled i.
- Flip a fair coin. Put x on the left and the new leaf on the right, or vice versa.
tree = single_leaf(label=0)
for i in 1..n:
x = uniformly_random_node(tree)
p = new_internal_node()
y = new_leaf(label=i)
replace x by p at x's old parent position
if fair_coin():
p.left = x
p.right = y
else:
p.left = y
p.right = x
return treeBefore step i, the tree has i-1 internal nodes, i leaves and therefore 2i-1 total nodes. There are 2(2i-1) possible graft choices when the left/right coin is included.
4. Work the First Three Steps by Hand
At size 0 there is one leaf: 0.
At step 1 there is only one possible node to choose. Insert a parent and leaf 1. The coin determines whether the leaves appear as (0,1) or (1,0).
At step 2 the current tree has three nodes: one internal node and two leaves. Choose any of the three with probability 1/3, then choose orientation with probability 1/2. There are therefore six equally likely decorated outcomes.
Do not rush past this tiny case. Draw all six outcomes and then erase the leaf labels. You will see that some unlabelled shapes appear through multiple labelings, but every Catalan shape receives the same total number of decorated realizations.
5. The Reverse Move Reveals the Proof
Suppose a final decorated tree has leaves labelled 0…n. Find the leaf labelled n. Let p be its parent and let x be its sibling. Remove leaf n and p, then reconnect x where p used to be. This uniquely reconstructs the previous decorated tree.
That reversibility means every decorated size-n tree corresponds to exactly one size-(n-1) decorated tree, one chosen node and one left/right orientation. There is no hidden many-to-one bias in the growth operation.
6. Counting Decorated Trees
Each unlabelled ordered full binary-tree shape with n internal nodes has n+1 leaves. If those leaves are decorated with labels 0…n, there are (n+1)! possible leaf labelings. Therefore the number of decorated trees is:
D_n = (n+1)! * C_n
= (2n)! / n!The Rémy growth step has 2(2n-1) possible choices from a decorated tree with n-1 internal nodes, giving the recurrence:
D_n = 2(2n-1) D_(n-1)Because each forward choice is uniform and each final decorated tree has one reverse predecessor, the decorated outputs are uniform.
7. Why Forgetting Labels Gives Uniform Shapes
Every unlabelled tree shape has exactly the same number, (n+1)!, of possible leaf decorations. Uniform sampling over decorated trees therefore induces uniform sampling over unlabelled ordered shapes once the labels are forgotten.
This is the second transferable proof pattern: sample uniformly in an enriched space where the recurrence is simple, then project down only when every target object has the same number of enrichments.
8. Linear-Time Implementation
If uniform node selection requires traversing the whole tree at every step, the implementation can drift toward O(n²). The standard engineering trick is to keep all current node references in an array. Since a full tree gains exactly two nodes per growth step—the new internal node and new leaf—the array can be updated incrementally.
Choosing an array index is O(1), as are pointer rewiring and appending the new nodes. The full generation can therefore run in O(n) time and O(n) space under the usual RAM model.
9. Parent Pointers and Root Replacement
The graft must replace x at its previous parent position. An implementation can store parent pointers, or represent child links through mutable references/indices. Root selection is a special case: if x is the root, the new internal node becomes the root.
A common bug is to update the new parent/children but forget to update x’s old parent link, producing a disconnected or cyclic structure.
10. Random Integer Selection Must Also Be Uniform
The mathematical proof assumes an exactly uniform choice among the 2i-1 current nodes and an unbiased orientation bit. In real code, using random_word % bound can introduce modulo bias unless the random-word range is an exact multiple of the bound.
For simulation, testing and combinatorial experiments, use a library’s correct uniform bounded-integer primitive or rejection sampling. The randomness mechanism is part of the algorithm’s statistical contract.
11. Random-Bit Cost
A straightforward implementation makes one bounded random choice at each growth step plus one orientation bit. This uses Θ(n log n) random bits in the usual model. Later work on holonomic samplers and entropy-efficient variants studies how to approach the information-theoretic minimum more closely while keeping near-linear or linear expected running time.
This is a useful professional distinction: time complexity, space complexity and randomness complexity are different resources.
12. Validate Uniformity Empirically Without Confusing It With Proof
For small n, enumerate every Catalan tree shape, generate a large sample, canonicalize each shape and count frequencies. A chi-squared diagnostic or confidence interval can reveal implementation bias. But empirical balance does not replace the bijective proof; it tests whether the code matches the proved algorithm.
Also test structural invariants on every sample:
- exactly n internal nodes;
- exactly n+1 leaves;
- every internal node has two children;
- no cycles;
- every node reachable from the root;
- if labels are retained, exactly one copy of each label 0…n.
13. Rémy Trees Are Not Random Binary Search Trees
A binary-search tree obtained by inserting a uniformly random permutation does not produce the same uniform distribution over tree shapes. Some shapes correspond to many more insertion permutations than others. Likewise, conditioned Galton–Watson trees, Boltzmann samplers and recursive Catalan samplers have their own distributions and implementation contracts.
Always name the target distribution, not just the data structure.
14. Why Exact Random Structures Matter
Uniform random tree generation is useful for average-case experiments, property testing, algorithm stress tests, combinatorial conjectures and probabilistic models. If the generator is biased, conclusions about “typical” trees can be biased too.
Rémy’s algorithm is therefore more than a curiosity: it teaches how a combinatorial counting identity can become an executable exact sampler.
15. How to Learn It Efficiently
Use a reconstruction-first progression. Draw the first two growth steps. Then take a decorated final tree and reverse it by deleting the largest leaf. Repeat until one leaf remains. Once the inverse is obvious, rebuild the forward code. This makes the uniformity proof feel inevitable instead of magical.
Common Failure States
- Choosing only leaves instead of all current internal and external nodes.
- Forgetting the fair left/right orientation choice.
- Sampling a bounded integer with modulo bias.
- Losing the root when the selected subtree is the root.
- Claiming uniformity over ordinary BST shapes generated by random insertions.
- Using O(n) traversal to select a random node at every step and then calling the implementation linear.
- Testing frequency balance without canonicalizing tree shapes correctly.
Practice Ladder
- Beginner: enumerate the Catalan shapes for n=0,1,2,3.
- Foundation: perform Rémy growth and reverse deletion by hand while keeping leaf labels.
- Intermediate: implement O(n) generation using an array of node references and parent-aware grafting.
- Advanced: prove uniformity through decorated-tree counting and the unique reverse operation.
- Professional: enumerate small-n shapes, statistically audit the sampler, measure random-bit consumption and compare with recursive Catalan and entropy-efficient samplers.
Learning Hall Boundary
This article owns exact uniform sampling of fixed-size ordered full binary trees through Rémy’s reversible grafting process. It does not replace general randomised algorithms, Wilson’s uniform spanning-tree sampler, binary-search-tree insertion analysis or generic tree data structures.
Evidence Boundary
Jean-Luc Rémy published the method in “Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire,” RAIRO Informatique Théorique 19(2), 1985, pp. 179–195. Later research has connected Rémy’s sampler to broader exact random-generation methods and has improved random-bit efficiency while preserving near-linear performance.
Professional rule: you understand Rémy’s algorithm when you can run the graft forward, invert it by deleting the newest leaf, derive the decorated-tree recurrence, and explain why equal decoration counts turn uniform decorated trees into uniform Catalan shapes.
