Serialize And Deserialize N Ary Tree - Leetcode Solution

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

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.

Solution:

To solve this problem, we can use a recursive approach. We will need to traverse the tree in a pre-order fashion while keeping track of the children of each node and their count. To serialize the tree, we will use a string builder to concatenate the data of each node along with the count of its children and recursively serialize its children.

To deserialize the tree, we will create a function that parses the string created during serialization, and recursively creates nodes and their children according to the information in the string.

Below is the implementation of the solution in Java:

Definition for a Node class:

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

public Node() {}

public Node(int _val) {
    val = _val;
}

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

}

Serialization function:

public String serialize(Node root) { StringBuilder sb = new StringBuilder(); serializeHelper(root, sb); return sb.toString(); }

private void serializeHelper(Node root, StringBuilder sb) { if (root == null) { sb.append("#"); return; }

sb.append(root.val);
sb.append("[");
sb.append(root.children.size());

for (Node child : root.children) {
    sb.append(" ");
    serializeHelper(child, sb);
}
sb.append("]");

}

Deserialization function:

public Node deserialize(String data) { int[] ptr = {0}; return deserializeHelper(data, ptr); }

private Node deserializeHelper(String data, int[] ptr) { if (ptr[0] >= data.length()) { return null; }

if (data.charAt(ptr[0]) == '#') {
    ptr[0]++;
    return null;
}

int val = 0;
while (data.charAt(ptr[0]) != '[') {
    val = val * 10 + (data.charAt(ptr[0]) - '0');
    ptr[0]++;
}

ptr[0]++;

List<Node> children = new ArrayList<>();
int childCount = 0;

while (data.charAt(ptr[0]) != ']') {
    Node child = deserializeHelper(data, ptr);
    children.add(child);
    childCount++;
}

ptr[0]++;

return new Node(val, children);

}

The serialization function takes a root node and returns the serialized string. It initializes a string builder and calls the serialization helper function with the root node and the string builder as arguments.

The serialization helper function first checks if the node is null. If it is, it appends the "#" symbol to the string and returns. Otherwise, it appends the value of the node to the string followed by the opening square bracket. It then appends the count of children nodes for the current node. Finally, it recursively calls itself for each child and appends their serialized values to the string.

The deserialization function takes a serialized string and returns the root node of the deserialized tree. It initializes an integer pointer to keep track of the current index of the string being parsed and calls the deserialization helper function with the string and the pointer as arguments.

The deserialization helper function first checks if the current index points to the "#" symbol. If it does, it increments the index and returns null. Otherwise, it reads the value of the node and initializes an empty list for the child nodes. It then loops over all child nodes, recursively calls itself for each child and appends the child to the list of children. Finally, it constructs a new node using the current value and the list of children, and returns it to the calling function.

Time Complexity:

The time complexity of both the serialization and deserialization functions is O(n), where n is the total number of nodes in the tree. This is because both functions traverse the entire tree once.

Space Complexity:

The space complexity of both functions is also O(n) because the size of the serialized string is proportional to the number of nodes in the tree, and the recursive stack space used by the deserialization function is also proportional to the same.

1