Serializing and De-serializing Binary Tree

Serializing a binary tree is easy. Only thing we need to do is to serialize null pointers as well. So a preorder traversal of the tree with a special symbol indicating null left or right child of the tree will be sufficient to reconstruct tree. In the example code below we indicate null by ~0 (which is the number with all 1 binary digit. For example if you have a tree like A->B->C (where B is a right child of A and C is a right child of B), the serialization will produce A NULL B NULL C NULL NULL. During reconstruction you start from the first element and proceed creating left child until you hit NULL. After we hit NULL, we drop it and look for nother element. If another element is not NULL we create right child. The process is straight forward and can easily be understood from the code.

  

std::vector<int> queue;

void serialize_bst(Node * node) {

 if(node == 0 )
 {
  queue.push_back(~0);
  return;
 }

 queue.push_back(node->value_);
 serialize_bst(node->left_);
 serialize_bst(node->right_);
}
 

  
Node* deserialize_bst(std::vector<int> &queue) {
 if(queue.empty())
  return 0;
 if(queue[0] == ~0) {
  queue.erase(queue.begin());
  return 0;
 }

 //creates node with null left and right child
 //and given value
 Node *node = new Node(0,0,queue[0]);
 queue.erase(queue.begin());
 node->left_ = deserialize_bst(queue);
 node->right_ = deserialize_bst(queue);
 return node;
}