# Encode N-ary Tree to Binary Tree

## Intuition

The algorithm I use is that, the left points to a linked list to represent the children list. And the right is been used as the linked list's next. For example, if we have a N-ary tree like below:

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

It could be changed to a binary tree like below:

```         1
/
3  -   2  -  4
/
5  - 6
```

## Solution

``````
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
"""
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Codec:

# Encodes an n-ary tree to a binary tree.
def encode(self, node: 'Node') -> TreeNode:
if node is None:
return None
binode = TreeNode(node.val)
if node.children:
binode.left = self.encode(node.children[0])
tmp = binode.left
for child in node.children[1:]:
tmp.right = self.encode(child)
tmp = tmp.right
return binode

# Decodes your binary tree to an n-ary tree.
def decode(self, binode: TreeNode) -> 'Node':
if binode is None:
return None
node = Node(binode.val, [])
tmp = binode.left
while tmp:
node.children.append(self.decode(tmp))
tmp = tmp.right
return node

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

``````