428. Serialize and Deserialize N-ary Tree

Problem Explanation:

We need to serialize and then deserialize an N-ary tree. Here serialization means to convert the tree structure into a string so we can store it into a file or transmit it across a network, and then bring it back into its original structure through deserialization.

For example, let us consider a 3-ary tree:

1     1
2  /  |  \
3 3   2   4
4/ \

5 6

We may serialize this into string: "1 3 2 4 5 6"

Now, the task is to convert this string back into its original tree structure through deserialization.

The problem states that there is no restriction on how the serialization/deserialization algorithm should work.

The only constraints are:

• N lies in the range of 1 to 1000.
• We should not use class member/global/static variables to store states.

Solution Approach:

The solution given here uses Breadth-First Search (BFS) to traverse the tree while serializing and deserializing the tree. We start with the root of the tree and form a queue to store the nodes. We pop nodes from the queue to check the children of the node and push the children into the queue. This is done until the queue is empty (i.e., all nodes are traversed).

Let's go through the example mentioned above:

• Serialize:

1. We start with the root node and add it to a queue
2. We keep on popping nodes from the queue, check its children, and add children into the queue. As we go through each node, we add its value into the serialized string. If a node has no children, we just add "n" to the string.
3. This is repeated until the queue is empty and all nodes are traversed.

• Deserialize:

1. Start by creating the root node from the first element from the serialized string and add it into a queue.
2. Next, go through each child of the node, create a node for each child and add it to the node's children.
3. Each child node is also added to the queue to be checked for its children.
4. This is repeated until the serialized string is completely traversed.

To see this in a more detailed form, we present a solution in Python below.

Python Solution:

1
2python
3class Node(object):
4    def __init__(self, val=0, children=0):
5        self.val = val
6        self.children = children
7
8class Codec:
9    def serialize(self, root):
10        if root is None:
11            return []
12
13        queue = [root]
14        result = [root.val]  # add root value
15
16        while queue:
17            node = queue.pop(0)
18            if node is None:
19                continue
20
21            for child in node.children:
22                queue.append(child)
23            result.append(len(node.children))  # add count of children
24            result.extend([child.val for child in node.children])  # add children values
25
26        return result
27
28    def deserialize(self, data):
29        if not data:
30            return None
31
32        root = Node(data[0])  # get root from first index
33        data = data[1:]  # remove root from data 
34        queue = [root]
35
36        while queue:
37            node = queue.pop(0)
38            if node is None:
39                continue
40
41            for _ in range(data.pop(0)):  # check children count
42                child = Node(data.pop(0))  # get child value
43                node.children.append(child)
44                queue.append(child)
45        
46        return root

In the above code, we first create a queue and push the root into the queue. While the queue is not empty, we pop a node from the queue and push the children of the current node into the queue. Here we also add the important information related to the node like its value and the count of children to the result array.

While deserializing, we start by popping nodes from the data and creating nodes for them. We keep popping as many nodes as the children count for the current node and add them to the node's children and the queue.

We repeat this process until all nodes are processed.## JavaScript Solution:

1
2javascript
3class Node {
4  constructor(val, children) {
5    this.val = val;
6    this.children = children;
7  }
8}
9
10class Codec {
11  serialize(root) {
12    if (root == null) return [];
13    let queue = [root];
14    let result = [root.val];
15    while (queue.length > 0) {
16      let node = queue.shift();
17      if (node == null) continue;
18      for (let child of node.children) {
19        queue.push(child);
20      }
21      result.push(node.children.length);
22      result.push(...node.children.map(child => child.val));
23    }
24    return result;
25  }
26
27  deserialize(data) {
28    if (data.length == 0) return null;
29    let root = new Node(data[0], []);
30    data = data.slice(1);
31    let queue = [root];
32    while (queue.length > 0) {
33      let node = queue.shift();
34      if (node == null) continue;
35      let count = data.shift();
36      for (var i = 0; i < count; i++) {
37        let child = new Node(data.shift(), []);
38        node.children.push(child);
39        queue.push(child);
40      }
41    }
42    return root;
43  }
44}

This JavaScript code mimics the approach of the Python solution. It uses a queue to store nodes and performs serialization and deserialization operations.

Java Solution:

1
2java
3import java.util.*;
4
5class Node {
6    public int val;
7    public List<Node> children;
8    public Node() {}
9    public Node(int _val) {
10        val = _val;
11    }
12    public Node(int _val, List<Node> _children) {
13        val = _val;
14        children = _children;
15    }
16}
17
18class Codec {
19    public String serialize(Node root) {
20        if (root == null) return null;
21        Queue<Node> queue = new LinkedList<>();
22        queue.offer(root);
23        StringBuilder sb = new StringBuilder();
24        sb.append(root.val).append(" ");
25        while (!queue.isEmpty()) {
26            Node node = queue.poll();
27            if (node == null) continue;
28            for (Node child : node.children) {
29                queue.offer(child);
30            }
31            sb.append(node.children.size()).append(" ");
32            for (Node child : node.children) {
33                sb.append(child.val).append(" ");
34            }
35        }
36        return sb.toString();
37    }
38
39    public Node deserialize(String data) {
40        if (data == null) return null;
41        String[] arr = data.split(" ");
42        Node root = new Node(Integer.parseInt(arr[0]), new ArrayList<>());
43        Queue<Node> queue = new LinkedList<>();
44        queue.offer(root);
45        int i = 1;
46        while (!queue.isEmpty()) {
47            Node node = queue.poll();
48            int count = Integer.parseInt(arr[i++]);
49            for (int j = 0; j < count; j++) {
50                Node child = new Node(Integer.parseInt(arr[i++]), new ArrayList<>());
51                node.children.add(child);
52                queue.offer(child);
53            }
54        }
55        return root;
56    }
57}

In the Java solution, we use the StringBuilder class for string concatenation to improve program performance. The rest of the logic is similar to the Python and JavaScript approach, using a queue to process the nodes and using the dequeuing operation to serialize/deserialize the tree.

Solution Implementation