Serialize/Deserialize Binary Tree
Given a binary tree, serialize it to a file and then deserialize it back to a tree.
Statement
Serialize a given binary tree to a file and then deserialize it back to a tree. Make sure 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.
Example
Consider the below tree as the input tree:
We’ll serialize our tree into a list of integers, and then we can write this list into a file. For simplicity, we won’t write anything in the files.
Sample input
The input list below represents the level-order traversal of the binary tree:
[100, 50, 200, 25, 75, 350]
Expected output
The sequence below represents the in-order traversal of the deserialized binary tree:
25, 50, 75, 100, 200, 350
Try it yourself
Note: The binary tree node’s class has members
leftandrightto store references to other nodes, along with the memberdatato hold the node’s value.
#include <iostream>#include <vector>#include <limits>#include "BinaryTree.cpp"using namespace std;vector<int> Serialize(BinaryTreeNode* root) {// TODO: Write - Your - Codereturn {};}BinaryTreeNode* Deserialize(vector<int>& stream) {// TODO: Write - Your - Codereturn nullptr;}
Solution
There can be multiple approaches to serialize and deserialize the tree. One way to serialize the tree is as follows:
-
Perform a depth-first traversal and serialize individual nodes to the stream.
-
We use a pre-order (root, left, right) traversal here.
-
We also serialize the marker to represent a null pointer to help deserialize the tree.
Consider the below binary tree as an example:
Markers ...