Serialize and Deserialize an N-ary tree
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

Question

Serialize and Deserialize an N-ary tree

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

Accepted Answer

Breadth First Search

Serialization - In serialization, we have to convert the tree into serial order. So we will put the tree node’s value in a vector in such a way that after every node’s child values we will append a ‘-1’.

We will maintain a queue that will store tree nodes. For every node, we will push its child node’s value in the vector and push its child nodes in the queue so that they can be explored further. After pushing all the child node’s value, we will push ‘-1’ to the vector. We will continuously explore all the nodes until the queue is not empty.

Algorithm

1. Serialization

Let ‘FILE’ be the vector/list that will store the serial order of the tree.
Create a queue ‘Q’ that will store nodes of the tree.
If the ROOT is NULL, return.
Push DATA of the ROOT in ‘FILE’ and ‘ROOT’ to queue.
Start traversing until the queue is not empty.
- Store the front node of the queue in “CURRENT_NODE” and pop out this front node.
- Push all the child node’s value of “CURRENT_NODE” in 'FILE'
- Push all the child nodes of “CURRENT_NODE” to ‘Q’
- After pushing all the child values, push ‘-1’ to “FILE”.

2. Deserialization

For deserialization, we have to convert the values in the vector ‘FILE’ to an N-ary tree. We will take a queue as we have maintained in serialization and initially push a node with data equal to FILE[ 0 ]. As we have appended ‘-1’ after child nodes of every node. So all the nodes before ‘-1’ will become child nodes of the node at the front of the queue.

So we will create nodes until ‘-1’ is encountered. All these nodes will be the child of the node at front of the queue and we will push all these nodes to ‘Q’ so that we can get the child nodes of these nodes also.

Algorithm

Create a queue ‘Q’ that will store nodes of the tree.
If FILE[ 0 ] = -1, i.e there is no root node, return NULL.
Create a node ‘ROOT’ with data value = FILE[ 0 ].
Push this ‘ROOT’ node to the queue.
Take a variable ‘INDEX’ that will store the index of ‘FILE’ that we have to deserialize. (initialized to 1)
Traverse through ‘Q’ until ‘Q’ is not empty.
- Store the front node of the queue in “CURRENT_NODE” and pop out this front node.
- Take a vector “CHILDREN” that will store all the child nodes of the ‘CURRENT_NODE’.
- Now traverse through ‘FILE’ from ‘INDEX’ until ‘-1’ is not encountered.
  - Create nodes with values FILE[ INDEX ] and push it to ‘CHILDREN’ and ‘Q’.
- Store this ‘CHILDREN’ vector to the child of “CURRENT_NODE”

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes of a tree.

We have used a queue that is storing the child nodes of a node. As the maximum number of children in the tree can be ‘N-1’. So space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes of a tree.

Every node of the tree is visited once. Therefore time complexity is of order O(N).

Python (3.5)

'''
	Time Complexity : O(N)
    Space Complexity : O(N)
  
    Where 'N' is the number of nodes of tree.
'''

from collections import deque 

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.child = []


def serialization(root, file):
    
    # If tree is empty.
    if root == None:
        file.append(-1)
        return
    
    # Push data into root.
    file.append(root.data)
    
    # Initialise a queue.
    q = deque()
    
    # Push root into queue.
    q.append(root)
    
    # Traverse through the queue.
    while len(q) > 0:
        
        # Store front of queue.
        currentNode = q.popleft()
        
        # Traverse.
        for j in range(len(currentNode.child)):
            node = currentNode.child[j]
            file.append(node.data)
            q.append(node)
            
        # Push -1.
        file.append(-1)
        

def deserialization(root, file):
    
    # Initialise data.
    data = file[0]
    
    # If data is -1 return root.
    if data == -1:
        return root
        
    root = TreeNode(data)
    
    # Initialise queue.
    q = deque()
    q.append(root)
    
    # Initialise variable.
    i = 1
    
    # Traverse through the queue.
    while len(q) > 0:
        
        # Store front of queue.
        currentNode = q.popleft()
        
        # Initialise variable.
        x = 0
        children = []
        
        # While true.
        while True:
            
            # Updated x.
            x = file[i]
            i += 1
            if x == -1:
                break
            else:
                node = TreeNode(x)
                children.append(node)
                q.append(node)
                
        # Update child of current.
        currentNode.child = children
        
    # Return root.
    return root

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)

  

    Where 'N' is the number of nodes of tree.

*/



#include



void serialization(TreeNode *root, vector &file)

{



    // If tree is empty.

    if (root == NULL)

    {

        file.push_back(-1);

        return;

    }



    // Push data into root.

    file.push_back(root -> data);



    // Initialise a queue.

    queue *> q;



    // Push root into queue.

    q.push(root);



    // Traverse through the queue.

    while (q.empty() == false)

    {



        // Store front of queue.

        TreeNode *currentNode = q.front();



        // Pop element.

        q.pop();



        // Traverse.

        for (int j = 0; j < (currentNode -> child).size(); j++)

        {

            TreeNode *node = currentNode -> child[j];

            file.push_back(node -> data);

            q.push(node);

        }



        // Push -1.

        file.push_back(-1);

    }

}



TreeNode *deserialization(TreeNode *root, vector &file)

{



    // Initialise data.

    int Data;

    Data = file[0];



    // If data is -1 return root.

    if (Data == -1)

    {

        return root;

    }



    root = new TreeNode(Data);



    // Initialise queue.

    queue *> q;

    q.push(root);



    // Initialise variable.

    int i = 1;



    // Traverse through the queue.

    while (q.empty() == false)

    {



        // Store front of queue.

        TreeNode *currentNode = q.front();

        q.pop();



        // Initialise variable.

        int x;

        vector *> children;



        // While true.

        while (1)

        {



            // Update x.

            x = file[i];

            i = i + 1;

            if (x == -1)

            {

                break;

            }

            else

            {

                TreeNode *node = new TreeNode(x);

                children.push_back(node);

                q.push(node);

                

            }

        }



        // Update child of current.

        currentNode -> child = children;

    }



    // Return root.

    return root;

}



TreeNode *SerDeser(TreeNode *root)

{



    // Serialisation.

    vector file;

    serialization(root, file);



    // Deserialisation.

    TreeNode *resNode = deserialization(NULL, file);

    return resNode;

}

Java (SE 1.8)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)
  
    Where 'N' is the number of nodes of tree.
*/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

	public static void serialization(TreeNode root, ArrayList file) {

		// If tree is empty.
		if (root == null) {
			file.add(-1);
			return;
		}

		// Push data into root.
		file.add(root.data);

		// Initialise a queue.
		Queue> q = new LinkedList>();

		// Push root into queue.
		q.add(root);

		// Traverse through the queue.
		while (q.isEmpty() == false) {

			// Store front of queue.
			TreeNode currentNode = q.peek();

			// Pop element.
			q.remove();

			// Traverse.
			for (int j = 0; j < (currentNode.child).size(); j++) {
				TreeNode node = currentNode.child.get(j);
				file.add(node.data);
				q.add(node);
			}

			// Push -1.
			file.add(-1);
		}
	}

	public static TreeNode deserialization(TreeNode root, ArrayList file) {

		// Initialise data.
		int Data;
		Data = file.get(0);

		// If data is -1 return root.
		if (Data == -1) {
			return root;
		}

		root = new TreeNode(Data);

		// Initialise queue.
		Queue> q = new LinkedList>();
		q.add(root);

		// Initialise variable.
		int i = 1;

		// Traverse through the queue.
		while (q.isEmpty() == false) {

			// Store front of queue.
			TreeNode currentNode = q.peek();
			q.remove();

			// Initialise variable.
			int x;
			ArrayList> children = new ArrayList>();

			// While true.
			while (true) {

				// Update x.
				x = file.get(i);
				i = i + 1;
				if (x == -1) {
					break;
				} else {
					TreeNode node = new TreeNode(x);
					children.add(node);
					q.add(node);

				}
			}

			// Update child of current.
			currentNode.child = children;
		}

		// Return root.
		return root;
	}

	public static TreeNode SerDeser(TreeNode root) {

		// Serialisation.
		ArrayList file = new ArrayList();

		serialization(root, file);

		// Deserialisation.
		TreeNode resNode = deserialization(null, file);
		return resNode;
	}
}

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:

Input Format:

Note :

Output Format:

Note:

Constraints

Top Goldman Sachs Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Goldman Sachs Software Engineer