Saving a binary search tree to a file

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.

C++:
01 void BSTtoFile(Node* headofstream& f)
02 {
03     if(head==NULL)
04         return;
05     f<<head->value<<” “;
06     BSTtoFile(head->left,f);
07     BSTtoFile(head->right,f);
08 }
09 
10 Node* vectorToBST(vector<int> v, int& start, int max)
11 {
12     if((start>=v.size())||v[start]>max)
13         return NULL;
14     Node* head=new Node;
15     head->value=v[start];
16     start++;
17     head->left=vectorToBST(v,start,head->value);
18     head->right=vectorToBST(v,start,max);
19     return head;
20 }
21 
22 Node* fileToBST(ifstream& f)
23 {
24     string s;
25     vector <int> v;
26     while(true){
27         f>>s;
28         if(f.eof())
29             break;
30         while((s==” “)&&(!f.eof()))
31             f>>s;
32         v.push_back(atoi(s.c_str()));
33     }
34     int start=0;
35     return vectorToBST(v,start,MAX);
36 }
Advertisements
This entry was posted in File operation, Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s