Efficient random sampling of binary and unary-binary trees via holonomic equations

We present a new uniform random sampler for binary trees with n internal nodes consuming 2n+Θ(log⁡(n)2) random bits on average. This makes it quasi-optimal and out-performs the classical Remy algorithm. We also present a sampler for unary-binary trees with n nodes taking Θ(n) random bits on average. Both are the first linear-time algorithms to be optimal up to a constant.