Feature #7: Serialize and Deserialize File System

Description

We want to make a remote sync utility for our OS that will allow us to copy a portion of the filesystem, rooted at a specific directory, to a distant machine. Therefore, the first step will be to create the same hierarchical directory structure on the remote machine. Our entire filesystem will be present in memory as an N-ary tree. We will use serialization to convert and store the N-ary tree into a string. This will save the state of the filesystem. We can recreate the N-ary tree when needed, using deserialization.

We will be given an N-ary tree with the root node r as the root of any specific directory. There is no restriction on how the serialization and deserialization algorithm will work. We will just need to ensure that the directory tree can be serialized to a string and that the string can be deserialized back to its original tree structure.

Let’s look at the following examples:

We are free to use our creativity to serialize and deserialize a directory structure.

Solution

Let’s start the solution with serialization. Here’s the algorithm for it:

1. Enqueue the root node r in a queue.
2. Dequeue the queue and store the node in a variable named cur. Count the number of children it has and add it to the children_count list.
3. Store the val(value) of the cur node in another list called result. Then, Enqueue all of the children of cur in the queue.
4. Repeat the second and the third steps until there are no more nodes left in the queue.

We will get two lists with this algorithm: result with the value of each node, and children_count with the number of children that each node has. We will return these lists as a combined string, like this:

n_child = ",".join(map(str,children_count)) 
n_res = 

...