# LeetCode 431: Encode N-ary Tree to Binary Tree

## Problem Restatement

We need to design a way to convert an N-ary tree into a binary tree and then reconstruct the original N-ary tree.

Two methods are required:

| Method | Meaning |
|---|---|
| `encode(root)` | Convert an N-ary tree into a binary tree |
| `decode(root)` | Convert the binary tree back into the original N-ary tree |

The conversion must preserve the full tree structure.

An N-ary tree node can have any number of children.

A binary tree node can only have:

| Pointer | Meaning |
|---|---|
| `left` | Left child |
| `right` | Right child |

So the main challenge is representing multiple N-ary children using only two binary pointers.

The official problem asks us to design the encoding and decoding logic ourselves. Any correct reversible representation is accepted. ([leetcode.com](https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input to `encode` | Root of an N-ary tree |
| Output from `encode` | Root of a binary tree |
| Input to `decode` | Root of the encoded binary tree |
| Output from `decode` | Original N-ary tree |
| Empty tree | Encode and decode as `None` |

Typical node definitions:

N-ary node:

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

Binary tree node:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

## Examples

Consider this N-ary tree:

```text
        1
      / | \
     2  3  4
       / \
      5   6
```

We encode it into this binary tree:

```text
        1
       /
      2
       \
        3
       / \
      5   4
       \
        6
```

This representation follows two rules:

| Binary Pointer | Meaning |
|---|---|
| `left` | First child |
| `right` | Next sibling |

For node `1`:

```text
1.left = 2
```

because `2` is the first child.

Then siblings are chained through `right`:

```text
2.right = 3
3.right = 4
```

For node `3`:

```text
3.left = 5
5.right = 6
```

because `5` and `6` are children of `3`.

This representation is called the left-child right-sibling representation.

## First Thought: Store Children in Arrays

One idea is to store child lists separately or use additional metadata.

However, the problem requires a pure binary tree structure.

We only have:

```text
left
right
```

So the encoding must use only those two pointers.

## Key Insight

The left-child right-sibling representation converts any N-ary tree into a binary tree.

The mapping is:

| N-ary Meaning | Binary Pointer |
|---|---|
| first child | `left` |
| next sibling | `right` |

Suppose an N-ary node has children:

```text
A, B, C, D
```

The binary representation becomes:

```text
parent.left = A
A.right = B
B.right = C
C.right = D
```

So:

1. The binary `left` pointer moves downward into children.
2. The binary `right` pointer moves sideways across siblings.

This transforms arbitrary branching into a standard binary tree.

## Algorithm

### Encoding

For an N-ary node:

1. Create a binary node with the same value.
2. If the node has children:
   - Encode the first child and store it in `left`.
3. For the remaining children:
   - Chain them through `right`.

### Decoding

For a binary node:

1. Create an N-ary node with the same value.
2. Traverse the binary `left` subtree:
   - The left child is the first N-ary child.
3. Follow `right` pointers:
   - Each right sibling becomes another N-ary child.
4. Recursively decode each child.

## Correctness

During encoding, every N-ary node becomes exactly one binary node with the same value.

For any N-ary node, its first child is stored in the binary `left` pointer. Every remaining child is linked through successive binary `right` pointers. Therefore, the full ordered child list is preserved.

Suppose an N-ary node has children:

```text
c1, c2, c3
```

The encoded binary structure becomes:

```text
left -> c1
c1.right -> c2
c2.right -> c3
```

This preserves both child membership and sibling order.

During decoding, we reverse this exact process. The binary `left` pointer identifies the first child. Following `right` pointers reconstructs the remaining siblings in order.

Because encoding preserves every node value and every parent-child relationship, and decoding reverses the same transformation exactly, the decoded tree is identical to the original N-ary tree.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every node is processed once |
| Space | `O(h)` | Recursion depth follows tree height |

Here, `n` is the number of nodes.

`h` is the maximum tree height.

## Implementation

```python
class Codec:
    def encode(self, root: 'Node') -> 'TreeNode':
        if not root:
            return None

        binary_root = TreeNode(root.val)

        if not root.children:
            return binary_root

        binary_root.left = self.encode(root.children[0])

        current = binary_root.left

        for child in root.children[1:]:
            current.right = self.encode(child)
            current = current.right

        return binary_root

    def decode(self, data: 'TreeNode') -> 'Node':
        if not data:
            return None

        nary_root = Node(data.val, [])

        current = data.left

        while current:
            nary_root.children.append(self.decode(current))
            current = current.right

        return nary_root
```

## Code Explanation

The encoder handles the empty tree first:

```python
if not root:
    return None
```

Then we create the binary node:

```python
binary_root = TreeNode(root.val)
```

The values are copied directly.

If the N-ary node has children:

```python
if not root.children:
    return binary_root
```

we encode the first child into the binary `left` pointer:

```python
binary_root.left = self.encode(root.children[0])
```

Then we connect the remaining siblings through `right` pointers:

```python
current = binary_root.left
```

For every later child:

```python
current.right = self.encode(child)
current = current.right
```

This creates the sibling chain.

The decoder reverses the process.

We create the N-ary node:

```python
nary_root = Node(data.val, [])
```

Then we move into the first child using:

```python
current = data.left
```

While siblings exist:

```python
while current:
```

we decode each sibling subtree and append it into the children list:

```python
nary_root.children.append(self.decode(current))
```

Then we move sideways through sibling links:

```python
current = current.right
```

Eventually, all children are reconstructed in order.

## Testing

We can test by encoding and then decoding trees and comparing the final structure.

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def same_nary(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_nary(x, y):
            return False

    return True

def run_tests():
    codec = Codec()

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

    binary = codec.encode(root)
    restored = codec.decode(binary)

    assert same_nary(root, restored)

    single = Node(10)
    assert same_nary(
        single,
        codec.decode(codec.encode(single)),
    )

    assert codec.encode(None) is None
    assert codec.decode(None) is None

    chain = Node(1, [
        Node(2, [
            Node(3, [
                Node(4),
            ]),
        ]),
    ])

    assert same_nary(
        chain,
        codec.decode(codec.encode(chain)),
    )

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Multi-child tree | Checks sibling encoding |
| Nested subtree | Checks recursive structure |
| Single node | Checks smallest tree |
| Empty tree | Checks `None` handling |
| Deep chain | Checks recursive depth |