Serialize a binary tree

#include <stdio.h>
#include <vector>
#include <string>
#include <boost/foreach.hpp>

#define foreach BOOST_FOREACH

using namespace std;

struct Node
int data;
Node *left;
Node *right;

Node(int d):data(d), left(NULL), right(NULL){}

typedef Node *Tree;

struct SerializedNode
int data; //this can be any type which is serializable
int parent; //index of the parent in the sequence
Node *node; //This is placeholder for dereferencing
bool isLeft;//tells whether this is left or right node

SerializedNode(int d, int p, bool l):data(d), parent(p), node(NULL), isLeft(l){}


void serialize(vector<SerializedNode> &v, Node *root, int parent, bool isLeft)
if(!root) return;
int size = v.size(); //index of the current node

v.push_back(SerializedNode(root->data, parent, isLeft));

serialize(v, root->left, size, true );
serialize(v, root->right, size, false);


Tree deserialize(vector<SerializedNode> &v)
foreach(SerializedNode &n, v)
n.node = new Node(;

if(n.parent != -1)
Node *parent =;

n.isLeft?parent->left = n.node : parent->right = n.node;

return v[0].node;

string serializeTree(Tree t)
vector<SerializedNode> v;

serialize(v, t, -1, false);
return string((char*)(&v[0], v.size() * sizeof(SerializedNode)));

Tree deserializeTree(string s)
const char *data = s.c_str();
size_t len = s.length();

vector<SerializedNode> v;

memcpy(&v[0], data, len);

return deserialize(v);

Leave a Reply

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

You are commenting using your 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