Here is an idea (that may not work).

Create an AVL — or any data structure that is backed by a self balancing binary tree.

Generate n random numbers and insert them one by one into said tree.

This will result in a binary tree that should be random enough for most uses.

I guess you can simply generate an array of ancestors as follows:

$$$p_k = \text{rng()} \mod k$$$, where $$$k \in [1, n)$$$

Then build a zero indexed tree with edges $$$(i, p_i)$$$. It can be proved that height of the tree is $$$O(\log(n))$$$. You can additionally shuffle vertices to get random enumeration of them as well.