CareerCup

use level-order traversal to write/read tree

here is a code to serialize and de-serialize a binary search tree. The key idea here is to serialize the BST in pre-order.

#include "BinaryTree.h"
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

static void serializeImp(btree *p, ofstream& sFile, char *buf)
{
        if(p == NULL)
                return;

        sprintf(buf, "%d", p->data);
        for(int i = 0; buf[i] != '\0'; i++)
                sFile.put(buf[i]);

        sFile.put(' ');
        serializeImp(p->left, sFile, buf);
        serializeImp(p->right, sFile, buf);
}

void serializeBST(btree *p, char *filename)
{
        char buffer[34];
        ofstream sFile(filename);
        serializeImp(p, sFile, buffer);
        sFile.close();
}

static bool getNextData(ifstream& inFile, char *buf)
{
        int i;
        char c;

        while(!inFile.eof() && (c = inFile.get()) == ' ');

        if(inFile.eof())
                return false;

        buf[0] = c;
        for(i = 1; !inFile.eof() && (c = inFile.get()) != ' '; i++)
                buf[i] = c;

        buf[i] = '\0';
        return true;
}

void deSerializeImp(btree **p, ifstream& inFile, int *val, char *buf, int min, int max)
{
        if(*val < min || *val > max)
                return;

        *p = createNode(*val);
        if(!getNextData(inFile, buf))
                return;
        *val = atoi(buf);

        deSerializeImp(&(*p)->left, inFile, val, buf, min, (*p)->data);
        deSerializeImp(&(*p)->right, inFile, val, buf, (*p)->data, max);
}

btree* deSerializeBST(char *filename)
{
        int val;
        btree *p = NULL;
        ifstream inFile(filename);
        char buffer[34];

        if(!getNextData(inFile, buffer))
                return NULL;
        val = atoi(buffer);

        deSerializeImp(&p, inFile, &val, buffer, INT_MIN, INT_MAX);
        inFile.close();
        return p;
}

int main(int argc, char *argv[])
{
        btree *head = NULL, *newTree = NULL;
        int arr[] = {30,20,10,40,35,50};
        if(argc != 2)
                cout << "invalid number of arguments" << endl;

        for(int i = 0; i < 6; i++)
                head = BinaryTree_insert(head, arr[i]);

        serializeBST(head, argv[1]);
        //newTree = deSerializeBST(argv[1]);
        return 0;
}

Use JSON :). It is very efficient. Just pre-order cannot construct a unique tree. So above solution is not correct. If you go that route you need in-order traversal as well which doubles up the storage space requirement.