I'd probably go with something like the wave function collapse algorithm. It should be possible to make it generate trees with somewhat uniform probability.