> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Serialize and Deserialize N-ary Tree

> Tested Python solution for LeetCode 428 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 428, [Hard](/catalog/hard). Topics: [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [String](/catalog/topics/string). [View on LeetCode](https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 428   # by problem number
lcpy gen -s serialize_and_deserialize_n_ary_tree   # by problem name
```

## 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]]`. Note that this is just an example, you do not necessarily need to follow this format.

Or you can follow LeetCode's level order traversal serialization format, where each group of children is separated by the null value. For example, the above tree may be serialized as `[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]`.

You do not necessarily need to follow the above-suggested formats, there are many more different formats that work so please be creative and come up with different approaches yourself.

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0400-0499/0428.Serialize%20and%20Deserialize%20N-ary%20Tree/images/narytreeexample.png)

```
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
```

![Example 2](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0400-0499/0428.Serialize%20and%20Deserialize%20N-ary%20Tree/images/sample_4_964.png)

```
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
```

```
Input: root = []
Output: []
```

### Constraints

* The number of nodes in the tree is in the range `[0, 10^4]`.
* `0 <= Node.val <= 10^4`.
* The height of the n-ary tree is less than or equal to `1000`.
* Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/serialize_and_deserialize_n_ary_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/serialize_and_deserialize_n_ary_tree/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


class Node:
    def __init__(self, val: int = 0, children: list[Node] | None = None) -> None:
        self.val = val
        self.children = children if children is not None else []


class Codec:
    # Time: O(n) for encode and decode
    # Space: O(n)
    def __init__(self) -> None:
        pass

    def encode(self, root: Node | None) -> str:
        vals: list[str] = []

        def dfs(node: Node | None) -> None:
            if node is None:
                return
            vals.append(str(node.val))
            vals.append(str(len(node.children)))
            for child in node.children:
                dfs(child)

        dfs(root)
        return ",".join(vals)

    def decode(self, data: str) -> Node | None:
        vals = [int(v) for v in data.split(",") if v != ""]
        pos = 0

        def dfs() -> Node | None:
            nonlocal pos
            if pos >= len(vals):
                return None
            node = Node(vals[pos])
            count = vals[pos + 1]
            pos += 2
            for _ in range(count):
                child = dfs()
                assert child is not None
                node.children.append(child)
            return node

        return dfs()
```

## Complexity

| Time | Space |
| - | - |
| O(n) for encode and decode | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.