TR-184: Generating Binary Trees at Random

Abstract

We give a new constructive proof of the Chung-Feller theorem. Our proof provides a new and simple linear-time algorithm for generating random binary trees; the algorithm uses numbers no bigger than n.