Encode N-ary tree to binary tree
You have been given an N-ary tree ‘N’ nodes with node ‘1’ as head of the tree. Encode the above N-ary tree into a binary tree such that if only the encoded binary tree was given to you, you could restore the N-ary tree from the encoded binary tree. You also need to write a function that could decode a given binary tree and return a N-ary tree as in input format.

Note:

There is no restriction on how you encode/decode the N-ary tree.

Example:

N-ary Tree is given as follows:- 6 1 -1 2 3 4 -1 5 -1 6 -1 -1 -1 -1 The above N-ary tree and its encoded binary tree can be represented as follows:-

The above binary tree can be represented as follows in their level order traversal:- 1 2 -1 5 3 -1 -1 6 4 -1 -1 -1 -1

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. The first line of input contains the elements of the tree in the level order form separated by a single space.

Note:

N-ary Tree is represented in their level order traversal. Each group of children is separated by -1.

Example:

1 -1 2 3 4 -1 5 -1 6 -1 -1 -1 -1 The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 1 -1 2 3 4 -1 5 -1 6 -1 -1 -1 -1

Output Format:

For each test case, for Encode function/method: return the binary tree. For Decode function/method: return the N-ary tree

Note:

1. The list/array storing binary tree must contain ‘N' + 1 element as nodes are numbered from 1 to ‘N’. The 'i'th element of the list/array must contain first the left child then the right child. 2. If a node does not have a left/right child just display that child as -1. 3. You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Encode N-ary tree to binary tree

You have been given an N-ary tree ‘N’ nodes with node ‘1’ as head of the tree. Encode the above N-ary tree into a binary tree such that if only the encoded binary tree was given to you, you could restore the N-ary tree from the encoded binary tree. You also need to write a function that could decode a given binary tree and return a N-ary tree as in input format.

Note:

There is no restriction on how you encode/decode the N-ary tree.

Example:

N-ary Tree is given as follows:-
6
1 -1 2 3 4 -1 5 -1 6 -1 -1 -1 -1
The above N-ary tree and its encoded binary tree can be represented as follows:-

subsequence

The above binary tree can be represented as follows in their level order traversal:-
1
2 -1
5 3
-1 -1 6 4
-1 -1 -1 -1

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases.

The first line of input contains the elements of the tree in the level order form separated by a single space.

Note:

N-ary Tree is represented in their level order traversal. Each group of children is separated by -1.

Example:

subsequence

1 -1
2 3 4 -1
5 -1 6 -1 -1
-1 -1

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 -1 2 3 4 -1 5 -1 6 -1 -1 -1 -1

Output Format:

For each test case, for Encode function/method: return the binary tree. For Decode function/method: return the N-ary tree

Note:

1. The list/array storing binary tree must contain ‘N' + 1 element as nodes are numbered from 1 to ‘N’. The 'i'th element of the list/array must contain first the left child then the right child.

2. If a node does not have a left/right child just display that child as -1.

3. You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 1000

Time Limit: 1 sec

Accepted Answer

The task is to encode an N-ary tree into a binary tree and then decode the binary tree back into the original N-ary tree.

Encode the N-ary tree by representing each node as a binary tree node with its first child as the left child and subsequent children as the right child.
To decode the binary tree, traverse the binary tree and for each node, create a new N-ary tree node with its left child as the first child and subsequent right children as siblings.
Use a level order traversal to encode and decode the trees.
The encoded binary tree should have N+1 elements in the list/array.
If a node does not have a left/right child, represent it as -1.
Handle the base case when the input is an empty tree.

Accepted Answer

Making right sibling right child.

We will convert the N-ary tree to a binary tree as follows:

The root of the Binary Tree is the Root of the N-ary Tree.
The leftmost child of a node in the N-ary is the Left child of that node in the Binary Tree.
The right sibling of any node in the N-ary Tree is the Right child of that node in the Binary Tree.

We can decode from binary tree to N-ary tree. 1’s left child is the leftmost child of 1 in the N-ary tree. 3 and 4 are siblings of 2. 5’s leftmost child of 2 in the N-ary tree. 6’s leftmost child of 3 in the N-ary tree. In this way, we can decode the N-ary tree from the binary tree.

The steps are as follows:

Declare a list/array ‘ANS’ to store left and right child initially initialized with -1.
If 'i’th node has at least 1 child, then the 1st child is its left child.
Then traverse children of 'i’th node. If there are still children left after this node then make the next child the right child of the current node.
Return ‘ANS’.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of vertices in the tree.

Since we created a Binary Tree and an N-ary of size ‘N’. Thus the space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of vertices in the tree.

Since we are just visiting each vertex twice. Thus the time complexity will be O(N).

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    Where 'N' denotes the number of vertices in the tree.
*/

// Function for encoding to Binary Tree.
BTreeNode < int > * encode(NTreeNode < int > * root) {
    if (root == NULL)
        return NULL;
    // Creating a new encode node.
    BTreeNode < int > * encoded = new BTreeNode < int > (root -> val);
    if (root -> child.size() > 0) {
        encoded -> left = encode(root -> child[0]);
    }

    // Recur for each of child.
    BTreeNode < int > * curr = encoded -> left;
    for (int i = 1; i < root -> child.size(); i++) {
        curr -> right = encode(root -> child[i]);
        curr = curr -> right;
    }
    return encoded;
}

// Function for decoding to N-Ary Tree.
NTreeNode < int > * decode(BTreeNode < int > * root) {
    if (root == NULL)
        return NULL;
    // Creating a new decode node.
    NTreeNode < int > * decoded = new NTreeNode < int > (root -> val);

    // Recur for all the right child.
    BTreeNode < int > * curr = root -> left;
    while (curr != NULL) {
        decoded -> child.push_back(decode(curr));
        curr = curr -> right;
    }
    return decoded;
}

Python (3.5)

"""
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    Where 'N' denotes the number of vertices in the tree.
"""

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class NTreeNode:
    def __init__(self, data):
        self.data = data

        self.child = []

# Function for encoding to Binary Tree.
def encode(root):

    if (root == None):
        return root

    # Creating a new encode node.
    encoded = BinaryTreeNode(root.data)

    if (len(root.child) > 0):
        encoded.left = encode(root.child[0])

    curr = encoded.left

    # Recur for each of child.
    for i in range(1, len(root.child)):
        curr.right = encode(root.child[i])
        curr = curr.right

    return encoded

# Function for decoding to N - Ary Tree.
def decode(root):
    if (root == None):
        return root

    # Creating a new decode node.
    decoded = NTreeNode(root.data)

    # Recur for all the right child.
    curr = root.left
    while (curr != None):
        decoded.child.append(decode(curr))
        curr = curr.right

    return decoded

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    Where 'N' denotes the number of vertices in the tree.
*/

public class Solution {
    // Function for encoding to Binary Tree.
    public static BTreeNode encode(NTreeNode root) {
        if (root == null) {
            return null;
        }
        // Creating a new encode node.
        BTreeNode encoded = new BTreeNode(root.data);
        if (root.child.size() > 0) {
            encoded.left = encode(root.child.get(0));
        }

        // Recur for each of child.
        BTreeNode curr = encoded.left;
        for (int i = 1; i < root.child.size(); i++) {
            curr.right = encode(root.child.get(i));
            curr = curr.right;
        }
        return encoded;
    }

    // Function for decoding to N-Ary Tree.
    public static NTreeNode decode(BTreeNode root) {
        if (root == null) {
            return null;
        }
        // Creating a new decode node.
        NTreeNode decoded = new NTreeNode(root.data);

        // Recur for all the right child.
        BTreeNode curr = root.left;
        while (curr != null) {
            decoded.child.add(decode(curr));
            curr = curr.right;
        }
        return decoded;
    }
}

Note:

Example:

Input Format:

Note:

Example:

Output Format:

Note:

Constraints:

Top JUSPAY Front end Developer interview questions & answers

Popular interview questions of Front end Developer