Make delicious recipes!

How can tree be serialized and deserialized?


Solution 1: If we can serialize/deserialize a generic OM, then the tree can also be handled by that approach. This can be done by making use of own memory manager which allocates memory planes such that all objects pointed to from an object fall in the same memory plane.

If that is true, then it means that all objects in the same plane are at some offset from the beginning of the memory plane. During serialization, one can make one pass through all the objects in one memory plane and convert their pointers to offsets by subtracting the memory plane starting pointer from them.

Then we write out the entire memory plane into the file.

When we reload the memory plane, we add the starting of the memory plane to each pointer (which was restored as an offset rather than a pointer) to get the correct pointer.

If the objects were not in one plane, then for serialization, one cannot subtract the lowest pointer among them from all pointers because that offset will not be the same on restoration (since objects are not in one plane, we will not be restoring them together, so they will occupy different memory positions such that the offsets from the lowest pointer will not be the same as they were before serialization).


Solution 2: An approach specific to trees is that you write out both the pre-order and in-order traversal of the tree and then reconstruct the tree by reading both these orders.


Solution 3: If we have a special marker for null child, then pre-order or level-order traversal can be used to serialize a tree and it can be easily deserialized in O(n). The special null markers help to terminate the branches and leave no room for ambihuity when constructing the tree. The same is not possible in post-order or level-order traversals because there children are printed first.


Solution 4: Can you restore the tree by storing level of each node along with in-order traversal of the tree? Just in-order traversal is not sufficient because given an incomplete tree, next node can be added anywhere (even if we have to add it in in-order fashion). So if level is fixed, then can we restore the tree completely?



(De)Serialization with a special marker for no children



If we write a special marker to indicate end of children for every node, then it is very easy to serialize and deserialize a tree.
It can in fact be extended to an n-ary tree as well.

Example: For the above tree, we can write it as: ABD$E$$C$ which would imply grouping like this:


ABD$E$$C$$

The following code can be used to serialize and deserialize.
void serialize(TreeNode root)
{
    if (root == null) return;
 
    writeToFile (root.data);
    if (root.children != null)
    {
        for (TreeNode child: root.children)
            serialize(child);
    }
 
    writeToFile (MARKER);
}
 
TreeNode deSerialize()
{
    char val = readFromFile();
    if ( val == MARKER )
       return null;
 
    TreeNode root = new TreeNode(val);
    while (true)
    {
      TreeNode child = deSerialize();
      if (child == null)
         break;
      root.children.add(child);
    }
 
    return root;
}

We can also write the number of children before writing any children of a node. This will obviate the need to write MARKER.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal