Convert N-ary Tree to Binary Tree

Statement

Convert a given n-aryAn n-ary tree is a type of tree data structure in which the nodes can hold a maximum of n children. tree to a binary tree structure. Then reconvert it to its original n-ary tree structure.

Example

Step 1: N-ary to binary tree conversion

Consider the following n-ary tree:

Sample input

The input list below represents the in-order traversal of the n-ary tree:

[2, 5, 6, 3, 1, 4]

There are several ways to represent the above n-ary tree as a binary tree. Look at the converted binary trees below (see if you get any clues):

Expected outputs

The sequences below represent the in-order traversal of the above two possible converted binary trees:

[4, 3, 5, 6, 2, 1]

[1, 2, 6, 5, 3, 4]

Note: There are other valid variations of binary trees that may result from an n-ary to binary ...