Serialize and Deserialize N-ary tree in java
This is a popular interview question asked in Tier-1 companies.
Given an n-ary tree, serialize and deserialize it.
Example of N-ary tree Serialization-Deserialization.
Algorithm
Serialization and Deserialization of N-ary tree is very similar to Serialization and Deserialization of Binary tree.
I would recommend to visit the Serialization/Deserialization post if not visited before: Serialize and Deserialize a Binary Tree
In Binary tree since there are only 2 child, we can get where is the start and end of the child of a particular Node from the serailized key, but in N-ary tree a Node can have n children, so we need some method to identify the start and end of a child nodes.
In this approach we will do a preorder traversal of N-ary tree and place the length of child nodes next to Node value as shown in example below, 
In Deserialization process, it is exactly reverse now, we know first key in the String is the actual node and next key is the length of child nodes of a key.
Java Program to Serialize Deserialize N-ary tree
package javabypatel;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class SerializeDeserializeNAryTree {
public static void main(String[] args) {
NAryNode root = new NAryNode(1,
Arrays.asList(
new NAryNode(2, Arrays.asList(
new NAryNode(5),
new NAryNode(6),
new NAryNode(7, Arrays.asList(
new NAryNode(11),
new NAryNode(12))))),
new NAryNode(3),
new NAryNode(4, Arrays.asList(
new NAryNode(8),
new NAryNode(9),
new NAryNode(10)))
));
String str = serializeTree(root, new StringBuilder());
System.out.println(str);
NAryNode deserializeRoot1 = deserializeApproach1(str == null? null : str.split(","), new int[1]);
NAryNode deserializeRoot2 = deserializeApproach2(str);
System.out.println(deserializeRoot1);
System.out.println(deserializeRoot2);
}
//In this approach, we need to take a separate index array of size 1 to remember the next element in array to pick
//or we can take a static integer to remember the state.
private static NAryNode deserializeApproach1(String[] arr, int[] index) {
if (arr == null || index[0] >= arr.length || arr[index[0]] == null) {
return null;
}
NAryNode n = new NAryNode(Integer.parseInt(arr[index[0]++]));
int size = Integer.parseInt(arr[index[0]++]);
n.child = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
n.child.add(deserializeApproach1(arr, index));
}
return n;
}
//In this approach, we are converting serialized tree to Queue, so that when we do
//queue.poll it will remove the element and we don't need to keep track of the next element to process.
private static NAryNode deserializeApproach2(String str) {
if (str == null) {
return null;
}
return deserializeHelper(new LinkedList<String>(Arrays.asList(str.split(","))));
}
private static NAryNode deserializeHelper(Queue<String> queue) {
if (queue.isEmpty()) {
return null;
}
NAryNode n = new NAryNode(Integer.parseInt(queue.poll()));
int size = Integer.parseInt(queue.poll());
n.child = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
n.child.add(deserializeHelper(queue));
}
return n;
}
private static String serializeTree(NAryNode root, StringBuilder sb) {
if (root == null) {
return null;
}
sb.append(root.data);
sb.append(",");
if (root.child != null) {
sb.append(root.child.size());
sb.append(",");
for (int i = 0; i<root.child.size(); i++) {
serializeTree(root.child.get(i), sb);
}
} else {
sb.append(0);
sb.append(",");
}
return sb.toString();
}
}
package javabypatel;
import java.util.List;
public class NAryNode {
public int data;
public List<NAryNode> child;
public NAryNode(int data, List<NAryNode> child) {
this.data = data;
this.child = child;
}
public NAryNode(int data) {
this.data = data;
}
}
You may also like to see
Advanced Java Multithreading Interview Questions & Answers
Type Casting Interview Questions and Answers In Java?
Exception Handling Interview Question-Answer
Method Overloading - Method Hiding Interview Question-Answer
How is ambiguous overloaded method call resolved in java?
Method Overriding rules in Java
Interface interview questions and answers in Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
