The Binary Search Tree Save and Restore Question
November 22nd, 2009
Here’s an interesting interview question I heard recently. “If you have a binary search tree in memory, how can you can save its data to a file, and then later restore the tree to its original configuration?” Like many interview questions, you need to first make sure you understand exactly what the interviewer is asking. The key part of the solution is the fact that the shape of a binary search tree depends entirely upon the order in which data is inserted. There are several solutions to this question. One of them is to traverse the tree in memory using a preorder (node-left-right) traversal, storing each data node as its read into a queue. Then write the queue to a file. To restore the tree, open the file, red each data node in turn, and insert into an initially empty tree.
Entry Filed under: Interviewing
Trackback this post