Convert a Generic Tree (n-ary tree) to Binary Tree

Binary Tree

The Binary tree is a hierarchical data structure consisting of nodes and edges, where each node has at most two children. The two children of a node are referred to as its left and right children. The node at the top of the binary tree is commonly known as the root. The nodes with no children are called leaves. 

We have covered the basic concepts required for this blog. Let's now move to the problem statement.

Problem Statement

We are given a generic tree consisting of n nodes. The job is to convert that generic tree into a binary tree.

Sample Example

Let's take a simple example to understand how conversion works.

Input

Output:

5 8 3 4 2 1

Pictorial Representation:

Explanation:

As you can see, the diagram above is a tree that satisfies the conditions of a binary tree. Also, note that we are printing output in preorder format. Hence the output is converted into a binary tree from a generic tree.

Now we have understood the problem, let's move further to learn about its solution. We will now discuss an approach to solve the above-stated problem.

Approach

We will use three simple rules that will easily convert any generic tree to a binary tree. Excited? Let me tell you the rules.

Rule 1: Root of binary tree = Root of the generic tree.

Rule 2: Left child of node in binary tree = Leftmost child of the node in the generic tree.

Rule 3: Right child of the node in the binary tree = Right sibling of the node in the generic tree. Here sibling means children of the same parent node.
Note: If a root node has only a right child in the generic tree, it will directly become the last node's rightmost child node following the root node in the binary tree. 

Now let's check the algorithm for the problem statement given above.

Algorithm

We will understand the algorithm stepwise. Let's go.

• Create a generic tree and call the "genericToBinary" function.
  
  
  • Check if the root node is null. If yes, return null.
     
  • Check if the root node has no children. If true, return the root as the node is already a leaf node.
     
  • Check if the root node has only one child. If yes, call the "genericToBinary" function recursively with the child node and set it as the left child of the current node in the binary tree.
     
  • If the root has multiple children, set the left child of the binary tree as the result of recursively calling the genericToBinary function with the first child node as the argument.
     
  • Set the right child of the binary tree as the result of recursively calling the genericToBinary function with the next sibling node as the argument.
     
  • Iterate over the remaining child nodes and set them as the left child of the rightmost node in the binary tree.
     
  • Return the root of the binary tree.
     
• Print the binary tree using the preorder traversal.

Dry Run

We have covered the problem statement, sample example, and algorithm. Let's now discuss the dry run for the above algorithm. We will take the same input as we took in the sample example.

Step 1: Here, first, we will check if the root is null. The answer is No. Now we will check if the root node has no children. Yes, it does. Now, the root has multiple children, so set the leftmost node of the root as the left node of the binary tree.

Step 2: Now we have a new node 8. We will again check all the conditions for this node. So, the node is not null and has children. So the leftmost node of the generic tree will be set as the left node of 8. 

Step 3: Again, we have a new node 3. We will again check all the conditions. Note that the first condition is false here; that is, check if the node is null, but the second condition (check if the root node has no children) is true. Hence it will return the root that is 3 here.

Step 4: Now, we will move to the right child of 3. It will check whether 3 has any right sibling or not. Yes, it has that is 4. So, the right child of 3 will be 4.

Step 5: Using recursion, the conditions will again be checked for node 4. The node is not null, but again 4 has no children. So 4 is a leaf node. Hence it will return the root. As we have checked node 3, we will move to node 8.

Step 6: Now, we will check if 8 has any right sibling. Yes, it has that is 2. So the right child of 8 will be 2.

Step 7: Now, all the conditions will be checked again. The node is not null. Also, it has no children. But if you notice, the right sibling of 2 is present in the generic tree that is 1. Hence it will come as the right child of node 2.

All the nodes from the generic tree are finished now. And we have our final binary tree.

Now that we are clear with the algorithm and dry run let's discuss the implementation of the above approach.

Must Read Recursive Binary Search.

C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

class TreeNode {
public:
    int data;
    TreeNode* left;
    TreeNode* right;
    vector<TreeNode*> child;
    TreeNode(int data) {
        this->data = data;
        this->left = this->right = NULL;
    }
};

TreeNode* genericToBinary(TreeNode* root) {   
    if (!root || root->child.size()==0) {
        return root;
    }

    root->left = genericToBinary(root->child[0]);
    if (root->child.size() == 1) {
        return root;
    }
    root->right = genericToBinary(root->child[1]);

    for (int i = 2; i < root->child.size(); i++) {
        TreeNode* rightNode = root->right;
        while (rightNode->left != NULL) {
            rightNode = rightNode->left;
        }
        rightNode->left = genericToBinary(root->child[i]);
    }

    return root;
}

void printTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    printTree(root->left);
    printTree(root->right);
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->child.push_back(new TreeNode(8));
    root->child.push_back(new TreeNode(2));
    root->child.push_back(new TreeNode(1));

    root->child[0]->child.push_back(new TreeNode(3));
    root->child[0]->child.push_back(new TreeNode(4));

    TreeNode* binaryTree = genericToBinary(root);

    printTree(binaryTree);
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time complexity

The time complexity of the above approach is O(N), where N is the number of nodes present in the generic tree. The time complexity is O(N) because we are traversing through all nodes once to make a binary tree from the given generic tree.

Space complexity

The space complexity of the above approach is O(N). We are using a recursive function; therefore, it will take the space for the recursive stack. Maximum recursive calls can go up to N (in the case of a skewed tree). Hence the total space complexity is O(N).

Frequently Asked Questions

What is a generic tree?

A generic tree or an n-ary tree is a type of tree data structure in which each node can have at most n children.

Are the preorder and inorder traversal of a generic tree and its converted binary tree the same?

Yes, the preorder and inorder traversal of a generic tree and its converted binary tree are the same. 

What is a binary tree?

A Binary Tree is a data structure having a root node and, at most, two children nodes. Each of these children forms the left subtree and the right subtree.

How do recursive functions work?

Recursive functions work by making functions call themselves. A recursive function either calls itself or another function to eventually call the original function.

What are the types of recursion?

The different types of recursion are linear or tree recursion, binary recursion, mutual recursion, nested recursion and tail recursion.

Conclusion

This article discusses the topic "Convert a Generic Tree to Binary Tree". In detail, we have seen the definition of generic and binary trees. We also discussed the problem statement, sample example, algorithm, and dry run. Along with this, we have discussed the code in c++ and time and space complexity.

We hope this blog has helped you enhance your knowledge on the topic "Convert a Generic Tree to Binary Tree". If you want to learn more, then check out our articles.

• An introduction to the binary trees
• N-ary trees
• Foldable Binary Tree
• Binary Tree vs Binary Search Tree

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your coding competency, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!