Generate a random binary tree

You want to generate a random binary tree on n nodes, such that each structurally different tree has the same chance of being generated as any other.

Suppose you have access to a random number generator oracle which generates an integer in $\{1,2,\dots, K\}$ (with probability $\dfrac{1}{K}$), given $K$ as an input ($K$ could be as large as you want).

Can you give an algorithm which generates an n node binary tree using $O(n)$ calls to the random number generator?

Can you do it using $O(1)$ calls?

[Solution]