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]
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]
No comments:
Post a Comment