> ## 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.

# Encode N-ary Tree to Binary Tree

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

LeetCode 431, [Hard](/catalog/hard). Topics: [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Design](/catalog/topics/design), [Binary Tree](/catalog/topics/binary-tree). [View on LeetCode](https://leetcode.com/problems/encode-n-ary-tree-to-binary-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 431   # by problem number
lcpy gen -s encode_n_ary_tree_to_binary_tree   # by problem name
```

## Problem

Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-ary tree structure.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.

For example, you may encode the following `3-ary` tree to a binary tree in this way: `Input: root = [1,null,3,2,4,null,5,6]`. Note that the above is just an example which *might or might not* work. You do not necessarily need to follow this format, 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/0431.Encode%20N-ary%20Tree%20to%20Binary%20Tree/images/narytreebinarytreeexample.png)

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

```
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]
```

```
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/encode_n_ary_tree_to_binary_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/encode_n_ary_tree_to_binary_tree/test_solution.py):

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

from leetcode_py import TreeNode


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)
    # Encoding: left child = first child, right child = next sibling
    def __init__(self) -> None:
        pass

    def encode(self, root: Node | None) -> TreeNode[int] | None:
        if root is None:
            return None
        bnode = TreeNode[int](root.val)
        prev: TreeNode[int] | None = None
        for child in root.children:
            child_b = self.encode(child)
            if prev is None:
                bnode.left = child_b
            else:
                prev.right = child_b
            prev = child_b
        return bnode

    def decode(self, data: TreeNode[int] | None) -> Node | None:
        if data is None:
            return None
        node = Node(data.val)
        children: list[Node] = []
        cur = data.left
        while cur is not None:
            child = self.decode(cur)
            assert child is not None
            children.append(child)
            cur = cur.right
        node.children = children
        return node
```

## 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.