Generate Large Binary Tree

Hard
Tree Random PRNG
🏢Jane Street
0 views0 likes

Problem Description

Generate Large Binary Tree

Create a function `generate()` that returns a binary tree. The tree should be finite but arbitrarily large, and the generation should be performed in constant time, O(1).

Example: 

Input: generate()
Output: TreeNode with potentially very large, but finite number of nodes

Constraints:

  • The function must run in O(1) time.
  • The tree generated must be finite but can be arbitrarily large.

Hints

Use a pseudorandom number generator (PRNG) to create the tree structure.

Ensure the tree generation logic runs in constant time.

Solution