I was asked this question in an interview of a start up.

Given a binary tree with billions of nodes. The tree will fit in memory. We have a quad-core system. How can we find a key efficiently in the tree? We can also assume that it is a balanced tree for this purpose.

My approach:

split the tree at level 2 or level 3 (depending on the number of threads that can execute in parallel at any time). After splitting the tree, get a vector of nodes where each node is a root of the splitted tree.

Trigger parallel threads to do the search in each of the subtree.

Then the discussion revolved around how to:

If one thread finds the key, then other threads should be cancelled. How to do this?
2 How to efficiently communicate the return value from the threads to main thread