Serialize/Deserialize Binary 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 left and right to store references to other nodes, along with the member data to hold the node’s value.

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 $(M*)$ ...