Problem

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.

Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following 3-ary tree

graph TB;
A[1] --- B[3] & C[2] & D[4]
B --- E[5] & F[6]

as [1 [3[5 6] 2 4]]. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Examples

Example 1:

1
2
3

Input：{1,3,2,4#2#3,5,6#4#5#6}
Output：{1,3,2,4#2#3,5,6#4#5#6}
Explanation：Pictured above

Example 2:

1
2
3
4
5
6

Input：{1,3,2#2#3}
Output：{1,3,2#2#3}
Explanation：
      1
	 / \
	3   2

Input format

This is how the Node structure and Codec structure looks:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class Codec {

    // Encodes a tree to a single string.
    public String serialize(Node root) {

    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {

    }

}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Solution

Method 1- Preorder DFS Recursion

In Binary Tree, we already know how many children are there, here we dont.

This is a template that can be applied to serialize and deserialize both binary and n-ary trees.

The only difference is that to serialize n-ary tree, we need to append the number of children of a node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Codec {

    // Encodes a tree to a single string.
    public String serialize(Node root) {
        StringBuilder sb = new StringBuilder();

        serial(sb, root);

        // System.out.println(sb.toString());
        return sb.toString();
    }

    private void serial(StringBuilder sb, Node root) {
        if (root == null) {
            sb.append("#");
            sb.append(",");
        } else {
            sb.append(root.val);
            sb.append(",");
            if (root.children != null) {
                sb.append(root.children.size());
                sb.append(",");
                for (Node child: root.children) {
                    serial(sb, child);
                }
            }
        }
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        Queue<String> queue = new LinkedList<String>(Arrays.asList(data.split(",")));

        return buildTree(queue);
    }

    private Node buildTree(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals("#")) {
            return null;
        }

        Node root = new Node(Integer.parseInt(val));
        int childrenCount = Integer.parseInt(queue.poll());

        root.children = new ArrayList<Node>();
        for (int i = 0; i <  childrenCount; i++) {
            root.children.add(buildTree(queue));
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Method 2 - Preorder DFS Using Parenthesis and Stack

When given tree like:

graph TB;
A[1] --- B[3] & C[2] & D[4]
B --- E[5] & F[6]

In an n-ary tree, there is no designated left or right child. We can store an ‘end of children’ marker with every node. The following diagram shows serialization where ] is used as end of children marker.

We can serialize N-ary tree like:

1

1[3[5[]6[]]2[]4[]]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Codec {

    // Encodes a tree to a single string.
    public String serialize(Node root) {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        sb.append("[");
        for (Node child : root.children) {
            sb.append(serialize(child));
        }
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        Node root = null;
        Stack<Node> stack = new Stack<>();
        int i = 0;

        while (i < data.length()) {
            int start = i;

            // Move pointer forward until we don't find a digit...
            while (i < data.length() && Character.isDigit(data.charAt(i))) {
                i++;
            }

            // If we haven't found a digit then we must have found the end of a child list...
            if (start == i) {
                Node child = stack.pop();
                if (stack.isEmpty()) {
                    root = child;
                    break;
                } else {
                    // Remove the child from the stack and assign it to the previous node on the stack
                    stack.peek().children.add(child);
                }
            } else {
                Node n = new Node();
                n.val = Integer.parseInt(data.substring(start, i));
                n.children = new ArrayList<>();
                stack.push(n);
            }
            i++;
        }
        return root;
    }
}