Microsoft Interview Question
Software Engineer / Developers//Serialize the tree.Writing the tree values to a file or array is serialization.
//Storing the data from the tree in an array. or we can store the node itself in an object array.We have to
//design accordingly.
public void Serialize(Node root,ref int []treeArray,ref int index)
{
if (root == null)
{
treeArray[index++] = -999;
}
else
{
treeArray[index++] = root.ID;
Serialize(root.Left, ref treeArray, ref index);
Serialize(root.Right, ref treeArray, ref index);
}
}
//DESerialize the tree.Creating the tree from the data stored in the file or array.
public Node DeSerialize(ref int[] treeArray, ref int index,int arrayCount)
{
if (treeArray[index] == -999 && index < arrayCount)
{
index++;
return null;
}
else
{
Node node = new Node();
node.ID = treeArray[index++];
node.Left = DeSerialize(ref treeArray, ref index,arrayCount);
node.Right = DeSerialize(ref treeArray,ref index,arrayCount);
return node;
}
}
//Complexity is O(n)
Please comment...
A solution can be to serialize the n-ary tree into a postfix notation and save to disk. A special token can be used to separate the children from the parent.
Then the tree can be deserialized using a stack.
How about creating a XML file from the given n-ary tree using level order traversal (similar breath first search in graphs)
- UB_Green January 05, 2011So if "a" has two children "b" and "c" and this is the graph to be serialized then we can make like
<Node>
a //Name of that current node
b,c //Comma separated children of the current node from left to right.
</Node>
<Node>
b
</Node>
<Node>
c
</Node>
With the help <Node> tag in the file, we know that the next line will be holding the current node and the following line will hold either the children of the currently referred node from left to right comma separated or the closing tag </Node> If we encounter the closing tag after the current node value, it indicates that the currently referred node is a left node.
So this has complexity of O(n) in serializing and de-serializing. It works for n-ary case in general.