How to Make a Huge Binary Tree Fast
This interesting interview problem was asked by Jane Street.
Generate a finite, but an arbitrarily large binary tree quickly in O(1).
generate() should return a tree whose size is unbounded but finite.
If we ignore the O(1) generation constraint, we can create an unbounded tree by using randomness.
That is, we can generate the
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
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.
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.
Ace your programming interview
Get a coding problem every day in your inbox!