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 🙂

Related Posts

  • Rotate matrix by 90 degrees in java
    20 May

    Rotate Matrix by 90 degrees in java

    Table of ContentsClockwise or Right Rotate a MatrixAnti-Clockwise or Left Rotate a MatrixHow to Rotate Matrix K Times? In this article, we will look into another interesting problem related to 2D Arrays. Given a Matrix of N X N Dimension we have to Rotate matrix by 90 degrees. We will perform Rotation both Clockwise i.e. […]

  • Data structures in java
    16 April

    Data Structures in java

    Table of ContentsArray Declare and initialize array in javaAdvantages of arrayDisadvantages of array ExampleArray practice programsStackStack implementation using ArrayStack implementation using LinkedListImplementationPractice ProgramsQueueQueue implementation using arrayQueue implementation using LinkedListImplementationLinkedListImplementationLinkedList Practice ProgramsBinary treeImplementationBinary tree practice programsBinary Search treeImplementationBinary search tree Practice programsTrieImplementationHeapImplementationGraphImplementation Inbuild data structures in javaStringHashMapLinkedHashMapArrayListLinkedListHashSet In this post, we will see about various data […]

  • 29 November

    Top 100+ Java coding interview questions

    Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]

  • 18 April

    Minimum Number of Jumps to reach last Index

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find Minimum Number of Jumps to reach last Index. Problem Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a […]

  • 20 February

    Inorder Successor in a Binary Search Tree

    Table of ContentsProblemSolutionAPPROACH – I :Approach – II:(i) If the target node has a right child :(ii) If the target node does not have a right child :Time Complexity Discussion If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to […]

  • 04 February

    LCA of a K-ary Tree in O(Sqrt(height))

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about how to find Lowest Common Ancestor of a K-ary Tree in O(Sqrt(height)).We have already seen how to find LCA of n-ary tree in O(n) complexity. Problem Given a […]

Leave a Reply

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

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.