Serialize/Deserialize Binary Tree

Problem Statement#

Serialize a binary tree to a file and then deserialize it back to a tree so that the original and the deserialized trees are identical.Serialize: write the tree in a file.Deserialize: read from a file and reconstruct the tree in memory.Consider the below tree as the input tree.

const int MARKER = numeric_limits<int>::min();
void serialize(BinaryTreeNode* node, ostream& sstream) {
  if (node == nullptr) {
    sstream.write((char*) &MARKER, sizeof(MARKER));
    return;
  }
  sstream.write((char*) &node->data, sizeof(node->data));
  serialize(node->left, sstream);
  serialize(node->right, sstream);
}
BinaryTreeNode* deserialize(istream& sstream) {
  if (sstream.eof()) {
    return nullptr;
  }
  int val;
  sstream.read((char*) &val, sizeof(val));
  if (val == MARKER) {
    return nullptr;
  }
  BinaryTreeNode* pNode = new BinaryTreeNode(val);
  pNode->left = deserialize(sstream);
  pNode->right = deserialize(sstream);
  return pNode;
}
void test(vector<int>& v, bool display_output = false) {
  cout << "Create BST" << endl;
  BinaryTreeNode* root = create_BST(v);
  if (display_output) {
    display_preorder(root);
  }
  cout << "Start Serialize" << endl;
  ofstream outfile("temp.class", ios::binary);
  serialize(root, outfile);
  outfile.close();
  cout << "Start De-Serialize" << endl;
  ifstream infile("temp.class", ios::binary);
  BinaryTreeNode* root2 = deserialize(infile);
  infile.close();
  if (display_output) {
    cout << "\nAfter:\n";
    display_preorder(root2);
    cout << endl << endl;
  }
  assert(are_identical_trees(root, root2));
}
int main(int argc, char const *argv[]) {
  vector<int> v = { 50, 25, 100 };
  test(v, true);
  
  v = {10 , 3, 8, 45, 9, 35, 69, 15, 12, 25, 24, 27, 13};
  test(v, true);
  v = create_random_vector(100);
  test(v, true);
  v = create_random_vector(2000000,
      numeric_limits<int>::max() - 10);
  cout << "\nRun big test" << endl;
  test(v, false);
  return 0;
}

Solution Explanation#

Runtime Complexity#

Linear, O(n).

Memory Complexity#

Logarithmic, O(logn).

Recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of the binary tree h. It will be O(logn) for a balanced tree and in the worst case can be O(n).

Solution Breakdown#

There can be multiple approaches to serialize and deserialize the tree. One approach is to perform a depth-first traversal and serialize individual nodes to the stream. We’ll use a pre-order traversal here. We’ll also serialize some marker to represent a null pointer to help deserialize the tree.

Consider the below binary tree as an example. Markers (M*) have been added in this tree to represent null nodes. The number with each marker i.e. 1 in M1, 2 in M2, merely represents the relative position of a marker in the stream.

Serialize/Deserialize Binary Tree

Problem Statement#

Hint#

Try it yourself#

Solution#

Solution Explanation#

Runtime Complexity#

Memory Complexity#

Solution Breakdown#