This interesting interview problem was asked by Jane Street.

Generate a finite, but an arbitrarily large binary tree quickly in O(1).

That is, generate() should return a tree whose size is unbounded but finite.

### Eager tree generation

If we ignore the O(1) generation constraint, we can create an unbounded tree by using randomness.

That is, we can generate the left and right sub-trees recursively X% of the time.

Since the question doesn’t have any constraints about the values the nodes can have, we’ll arbitrarily set it to 0.

### Lazy tree generation

The trick here is that we can generate the tree lazily. Here we use Python’s property keyword, which lets us define a property on an object at look-up.

When the left or right property is looked up, we check if that sub-tree has been evaluated. If not, we recursively create a new node half the time. If it has been evaluated already, then we just return that node.

The object is created in constant time since none of the subtrees are evaluated when it’s created.

Are you interviewing for programming jobs, or do you just enjoy fun programming questions? Check out our newsletter, Daily Coding Problem, to get a question in your inbox every day.