New update is available. Click here to update.

Serialize and Deserialize an N-ary tree

Posted: 27 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given an N-ary tree where every node has at most ‘N’ child nodes. You need to first serialize it and then deserialize the serialized tree.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

In simple words, serialization is a process to store a tree in a file so that it can be later restored to its original form. Deserialization is reading the tree back from the file.

Note:
Note that the structure of the tree must be maintained while serialization and deserialization. Also, you can use any method to serialize or deserialize the tree. You just need to see that the tree can be serialized into a string and further deserialized into the original tree.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains elements of the N-ary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is changed, we take -1. To get the next node

The first not-null node(of the previous level) is treated as the parent of the first nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next nodes of the current level and so on.

The input ends when all nodes at the last level are null(-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the below-depicted tree, the input will be given as:
1 -1 2 3 4 -1 5 6 -1 -1 -1 -1 -1

Output Format:
For each test case, you need to print the deserialized tree after its serialization.

Print the output of each test case in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
1 <=  N <= 10^4

Time limit: 1 sec