Serialize and Deserialize N-ary Tree

XXX. Serialize and Deserialize N-ary Tree

Tree

Recursion

Serialization

Problem Statement:

Given the root of an N-ary tree, implement two functions:

• serialize: Convert the tree into a single string for storage or transmission.
• deserialize: Reconstruct the original tree from the serialized string.

The tree is represented using Node objects, where each node has a value and a list of children.

Algorithm:

The solution uses recursion for both serialization and deserialization:

1. For serialize:
   • Append the value of the node, followed by the number of its children, separated by commas.
   • Recurse for each child and append their serialized strings.
2. For deserialize:
   • Split the serialized string into tokens and use a queue to process them.
   • Extract the value and the number of children for each node, and recursively reconstruct the children.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once during serialization and deserialization.
Space Complexity: O(n), for the recursion stack and the queue used during deserialization.

Java Implementation:

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

        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(Node root, StringBuilder sb) {
        sb.append(root.val).append(','); // Append value
        sb.append(root.children.size()).append(','); // Append number of children

        for (Node child : root.children) 
            serialize(child, sb); // Recurse for each child
    }

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

    private Node deserialize(Queue q) {
        if (q.isEmpty()) return null;

        int val = Integer.valueOf(q.poll()); // Get node value
        int numChildren = Integer.valueOf(q.poll()); // Get number of children

        Node curr = new Node(val, new ArrayList<>());

        for (int i = 0; i < numChildren; i++) 
            curr.children.add(deserialize(q)); // Recurse for children

        return curr;    
    }  
}

class Node {
    public int val;
    public List children;

    public Node() {}

    public Node(int _val) {
        val = _val;
        children = new ArrayList<>();
    }

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