LeetCode Solutions Blog

Serialize and Deserialize N-ary Tree

Number: 765

Difficulty: Hard

Paid? Yes

Problem Description

Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node can have no more than N children. The goal is to convert the tree structure into a string (serialization) and then reconstruct the original tree from this string (deserialization). There is no strict format required as long as the tree can be correctly serialized and deserialized.

Key Insights

We can use a pre-order depth-first search (DFS) traversal to serialize the tree.
Each node will be recorded by its value followed by the number of its children.
During deserialization, the token stream is read sequentially to rebuild the tree structure recursively.
This approach ensures that the tree structure is properly captured and recreated without ambiguity.

Space and Time Complexity

Time Complexity: O(n) for both serialization and deserialization, where n is the number of nodes. Space Complexity: O(n) due to the recursion stack and storage of serialized tokens.

Solution

The solution uses a DFS approach to traverse the tree. During serialization, for each node we output its value and the count of its children. This allows the deserialization function to know how many subsequent tokens (representing serialized children) belong to the current node. The deserialization function uses a recursive helper that consumes tokens from a list (or iterator) to rebuild the tree. This method guarantees that the structure, including when a node has no children, is correctly captured and later reconstructed.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Codec:
    def serialize(self, root):
        # This function serializes an N-ary tree to a single string.
        tokens = []
        
        def dfs(node):
            if not node:
                return
            # Append the node value and the number of children.
            tokens.append(str(node.val))
            tokens.append(str(len(node.children)))
            # Recursively serialize each child.
            for child in node.children:
                dfs(child)
        
        dfs(root)
        return " ".join(tokens)

    def deserialize(self, data):
        # This function deserializes the encoded data string to an N-ary tree.
        if not data:
            return None
        tokens = data.split()
        # Using an iterator so that recursive calls can consume tokens sequentially.
        self.index = 0
        
        def dfs():
            if self.index >= len(tokens):
                return None
            # Create a node with the current token value.
            node_val = int(tokens[self.index])
            self.index += 1
            # Next token indicates the number of children.
            count = int(tokens[self.index])
            self.index += 1
            node = Node(node_val, [])
            # Recursively build each child.
            for _ in range(count):
                child = dfs()
                node.children.append(child)
            return node
        
        return dfs()

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