Serialize and Deserialize n-ary tree

Table of Contents

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.


Problem

Given a Generic Tree, Serialize and Deserialize it.
Serialization is a basically a representation of a tree in a String format which takes much lesser space than storing the tree itself.
Deserialization is constructing the actual tree using the the serialized format of the tree.

SerializationDeSerializationTree

OUTPUT:

Serialized Tree :
1 2 5 ) 6 ) ) 3 ) 4 7 ) 8 9 ) ) ) )

Deserialized Tree :
1 => [ 2 3 4 ] 2 => [ 5 6 ] 5 => [ ] 6 => [ ] 3 => [ ] 4 => [ 7 8 ] 7 => [ ] 8 => [ 9 ] 9 => [ ]


Solution

Serialization is just a traversal of the tree which can be either preorder or a postorder in which we insert an ‘end of subtree’ flag in the serialized string of the tree which helps us constructing the original tree while deserializing it.

SERIALIZATION:

We traverse in preorder in the tree and whenever we visit a new node we store it in the serialized string and in a set so that whenever we visit an already visited node we do not add in the serialized string.
whenever we return from a node, we append an end of subtree/child' flag in the string so that we keep a track on number of children / subtrees under that node.

DESERIALIZATION:

While deserializing the tree using the serialized string, we use a stack to keep the track of parent of the incoming node. So we will keep pushing the nodes into the stack until we get an ‘end of subtree’ marker, lets say we denote it by ‘)’,  if we get ‘)’ , we pop a node from stack and make it the child of the node at top of the stack. We keep on doing the same until we are finished with the given serialized string of the tree and eventually the original tree will be constructed. We traverse once again in preorder to print the constructed tree.

When you run above code, you will get below output

Serialized Tree :
1 2 5 ) 6 ) ) 3 ) 4 7 ) 8 9 ) ) ) )
Deserialized Tree :
1 => [ 2 3 4 ] 2 => [ 5 6 ] 5 => [ ] 6 => [ ] 3 => [ ] 4 => [ 7 8 ]

Comment in case of any doubts or Edits, Happy Learning 🙂

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *