deepSWE.io

Serialize and Deserialize N-Ary Tree

Trees

Problem Statement

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.

Example

Algorithm Explanation

We can use a pre-order traversal to serialize the tree. To handle the N-ary nature, we need to store the number of children for each node.

Algorithm Steps

Serialization: We'll perform a pre-order traversal. For each node, we append its value and the number of its children to our serialized string. Then, we recursively call on each child.
Deserialization: We'll use a queue to process the serialized string. We read the first value as the root. Then we read the number of its children and recursively build the subtrees for each child.

Start

Starting serialization process using pre-order traversal.

Serialized String:

Serialize and Deserialize N-Ary Tree Solution


class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        if not root:
            return ""
        
        parts = [str(root.val), str(len(root.children))]
        for child in root.children:
            parts.append(self.serialize(child))
        
        return " ".join(parts)

    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        if not data:
            return None
        
        parts = data.split(' ')
        
        def build_tree():
            val = int(parts.pop(0))
            num_children = int(parts.pop(0))
            node = Node(val, [])
            for _ in range(num_children):
                node.children.append(build_tree())
            return node

        return build_tree()