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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import random

class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

def generate():
root = Node(0)

if random.random() < 0.5:
root.left = generate()
if random.random() < 0.5:
root.right = generate()

return root

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self._left = left
self._right = right

self._is_left_evaluated = False
self._is_right_evaluated = False


@property
def left(self):
if not self._is_left_evaluated:
if random.random() < 0.5:
self._left = Node(0)

self._is_left_evaluated = True
return self._left

@property
def right(self):
if not self._is_right_evaluated:
if random.random() < 0.5:
self._right = Node(0)

self._is_right_evaluated = True
return self._right

def generate():
return Node(0)

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.