LeetCode 428: Serialize and Deserialize N-ary Tree

Problem Restatement

We are given an N-ary tree.

An N-ary tree is a rooted tree where each node can have zero or more children.

We need to design two methods:

There is no required serialization format. We can choose any format as long as it can rebuild the same tree structure.

The solution should be stateless. We should not use class-level, global, or static variables to store decoding state. The problem also states that N is in the range [1, 1000].

Input and Output

The node class usually looks like this:

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

Examples

Consider this tree:

        1
      / | \
     3  2  4
    / \
   5   6

One valid serialization is:

1 3 3 2 5 0 6 0 2 0 4 0

This means:

1 has 3 children
3 has 2 children
5 has 0 children
6 has 0 children
2 has 0 children
4 has 0 children

The exact format does not matter. What matters is that deserialize(serialize(root)) returns the same tree.

For an empty tree:

root = None

we serialize it as:

and deserialize it back to:

None

First Thought: Store Values Only

A first attempt might store only preorder values:

1 3 5 6 2 4

This loses structure.

From these values alone, we cannot know whether 5 and 6 are children of 3, or whether they are siblings of 3.

So each node must store two pieces of information:

Key Insight

Preorder traversal is enough if we store the child count with every node.

For each node, serialize:

value child_count

Then recursively serialize each child.

For the example tree:

        1
      / | \
     3  2  4
    / \
   5   6

we write:

1 3
3 2
5 0
6 0
2 0
4 0

Flattened into one string:

1 3 3 2 5 0 6 0 2 0 4 0

During deserialization, we read tokens from left to right.

When we read:

value child_count

we create a node, then recursively read exactly child_count children.

This is what makes the format unambiguous.

Algorithm

For serialization:

1. If root is None, return an empty string.
2. Run preorder DFS.
3. For each node, append:
   • node value
   • number of children
4. Join all tokens with spaces.

For deserialization:

1. If data is empty, return None.
2. Split the string into tokens.
3. Use an index to read tokens from left to right.
4. Read one node:
   • first token is value
   • second token is child count
5. Recursively read that many children.
6. Return the node.

The decoding index is local to deserialize, so the solution remains stateless.

Correctness

Serialization writes every node before its children. For each node, it also writes the number of children.

During deserialization, when we read a node value and child count, the child count tells us exactly how many child subtrees belong to that node.

Because serialization writes child subtrees immediately after the parent, deserialization reads them in the same order. The first child written becomes the first child reconstructed, the second child written becomes the second child reconstructed, and so on.

A leaf node has child count 0, so deserialization creates the node and returns immediately. An internal node has positive child count, so deserialization recursively reconstructs exactly that many children.

By induction over the preorder sequence, every serialized subtree is reconstructed with the same root value and the same ordered list of children. Therefore, deserialize(serialize(root)) reconstructs the original N-ary tree.

Complexity

Here, n is the number of nodes.

Implementation

class Codec:
    def serialize(self, root: 'Node') -> str:
        if root is None:
            return ""

        tokens = []

        def dfs(node: 'Node') -> None:
            tokens.append(str(node.val))
            tokens.append(str(len(node.children)))

            for child in node.children:
                dfs(child)

        dfs(root)
        return " ".join(tokens)

    def deserialize(self, data: str) -> 'Node':
        if not data:
            return None

        tokens = data.split()
        index = 0

        def build() -> 'Node':
            nonlocal index

            val = int(tokens[index])
            index += 1

            child_count = int(tokens[index])
            index += 1

            node = Node(val, [])

            for _ in range(child_count):
                node.children.append(build())

            return node

        return build()

Code Explanation

The serializer handles the empty tree first:

if root is None:
    return ""

For a non-empty tree, we store tokens in a list:

tokens = []

The DFS writes the current node before its children:

tokens.append(str(node.val))
tokens.append(str(len(node.children)))

This pair is enough to decode the node later.

Then we serialize every child in order:

for child in node.children:
    dfs(child)

Finally, we join all tokens:

return " ".join(tokens)

The deserializer first handles the empty string:

if not data:
    return None

Then it splits the string:

tokens = data.split()

The local variable index tells us which token to read next.

Inside build, we read the node value:

val = int(tokens[index])
index += 1

Then we read the number of children:

child_count = int(tokens[index])
index += 1

Now we can create the node:

node = Node(val, [])

Because child_count tells us exactly how many children to read, we recursively build that many child subtrees:

for _ in range(child_count):
    node.children.append(build())

The method returns the reconstructed root.

Testing

We can test by serializing a tree, deserializing it, then comparing both trees structurally.

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

def same_tree(a, b):
    if a is None or b is None:
        return a is b

    if a.val != b.val:
        return False

    if len(a.children) != len(b.children):
        return False

    for x, y in zip(a.children, b.children):
        if not same_tree(x, y):
            return False

    return True

def run_tests():
    codec = Codec()

    root = Node(1, [
        Node(3, [Node(5), Node(6)]),
        Node(2),
        Node(4),
    ])

    data = codec.serialize(root)
    restored = codec.deserialize(data)

    assert same_tree(root, restored)

    single = Node(10)
    assert same_tree(single, codec.deserialize(codec.serialize(single)))

    assert codec.serialize(None) == ""
    assert codec.deserialize("") is None

    chain = Node(1, [Node(2, [Node(3, [Node(4)])])])
    assert same_tree(chain, codec.deserialize(codec.serialize(chain)))

    print("all tests passed")

run_tests()

Test meaning: