Friday, March 18, 2011

Saving a Binary Search Tree to a File

Q: Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be “resurrected” later in the same or another computer environment.

Pre-order traversal is the perfect algorithm for making a copy of a BST. We can store the preorder traversal of the tree into File and then read it again to construct the tree. Assuming we have a file where the pre order traversal of the tree is written to it, We will now see how to read the file to construct that into BST.

No comments: