428. Serialize and Deserialize N-ary Tree

Resolves: #210

Firstly, this problem has quite a many possible solutions. There are many creative ways of packing a data structure like a tree into a string form. However, here, I am only going to be considering ones that are the most useful, to learn about or to actually use.

Approach 1-Nested Lists of Children

By using the recursive definition of the trees, we can encode each tree in the following form:

encode(T):
if T = null: ""
else: T.val+"["+encode(every child of T)+"]"

We can thus encode trees into relatively readable structures like: 9[27[0[]18[9[]]]54[]63[999[]]]

For the decoding, we simply check if there are characters, node values that we can read. If so, we add a node to our nodes stack. After that, if there are new integer values, that means that there are new nodes and we similarly add them. We don't encounter any integer values, that means that the last node in the stack has come to an end. Then we pop it and add it as a child to the previous node in the stack. If popping it makes the stack empty, it implies that this the node that we return as the root.

We can also implement this using recursion, it's however a bit more complex in Java because of passing by reference/value issues.

Approach 2-Level Order Encoding with Extended ASCII/Unicode Characters as Child Count

To denote that the children of a node has come to an end, we can put a termination character such as '#'. A node with value 9 with children 999, 18 and 36 would then look like this: 9999#18#36## The problem is that the values of root and the first children are concatenated if we add them like this. Instead of this, we can add them as character values. Instead of 9, we would add '0'=48(>ASCII code of '#') to it. Same for 999. Then, the encoding would look like this but as a string: [\u0057, \u1047, '#', \u0066 and so on

For decoding, we basically treat all the characters up to some termination point as the node's children. Since the nodes themselves would also look for their termination points, the end of the root won't mix up with the end of their children.

Approach 3-Level Order Encoding with Child Count + DFS Decoding

We can decode each node with the number of their children: A node with 4 children can be encoded as: root_val, 4, ... We can recursively encode the nodes of a tree like this. We do write '0' for leaf nodes too.

Decoding is quite easy here. We first split all the substring that were separated by commas and put them into a queue. The first value we poll is the root, second its children count. We recursively decode next count nodes as the children of this node. The recurrence takes care of preventing any confusions of polling and decoding.

spiralgo / algorithms