Encode N-ary Tree to Binary Tree

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-nary tree structure.

For example, you may encode the following3-arytree to a binary tree in this way:

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.

Note:

1. Nis in the range of [1, 1000]

2. Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

Solution

There are a lot of solutions to convert a N-ary tree to a binary tree. We only introduce one classical solution.

The strategy follows two rules:

1. Theleft childof each node in the binary tree isthe next siblingof the node in the N-ary tree.

2. Theright childof each node in the binary tree isthe first childof the node in the N-ary tree.

Using this strategy, you can convert a N-ary tree to a binary tree recursively. Also, you can recover the N-ary tree from the binary tree you converted.

The recursion recovery strategy for each node is:

1. Deal with its children recursively.

2. Add itsleft childasthe next child of its parentif it has a left child.

3. Add itsright childasthe first child of the node itselfif it has a right child.