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