Building uniformly random subtrees

We prove the existence of, and describe, a (random) process which builds subtrees of a rooted d-branching tree one node at a time, in such a way that the subtree created at stage n is precisely a uniformly random subtree of size n. The union of these subtrees is a ``uniformly random{''} infinite subtree, which we describe and generate in several ways. Generalization to generation of other combinatorial structures is also considered. (C) 2004 Wiley Periodicals, Inc.