Convert a generic tree (n-ary tree) to binary tree

Shreya Deep
Last Updated: May 13, 2022

Introduction

Generic trees and binary trees are two different yet very crucial data structures. These are hierarchical data structures and are not linear. They are generally used in cases where a data group has some relation

Let’s understand their definition and convert a generic tree into a binary tree.

What is a generic tree?

generic tree or an n-ary tree is a type of tree data structure in which each node can have at most n children, and n can be any integer value. In each node, there is a children vector that stores the addresses of the children of that node. The end nodes or the leaf nodes have no children.

Example

To read more in detail about generic trees, refer to this.

What is a binary tree?

Binary Tree is a Data Structure having a root node and at most two children nodes. Each of these children forms the left and right subtrees. The end nodes or the leaf nodes have no children and are pointed by a NULL pointer. 

Example:

To read more about binary trees, refer to this.

Conversion of a generic tree into a binary tree

The straightaway steps to convert a generic tree into a binary tree are:

  • The root of both the trees is the same.
  • The leftmost child of a node in a generic tree remains the left child of the same node in the binary tree.
  • The node which is just next towards the right direction to the current node(i.e., sibling) becomes the right child of the current node.


Note: In the generic tree, if a node has only one child in its right, then, in the binary tree, this right child node will become the right child of the last node following the parent node.

Example: 

Generic tree - 

Converted Binary tree - 

Steps of above conversion:

  • First, the root will be the same. Thus, make the root 1.
  • The left child of the root in the generic tree will also be the left child of the root in the binary tree. Thus, the left child of 1 is 2.
  • Since 2,3 and 4 are siblings, three will be the right child of 2, and 4 will be the right child of 3.
  • Now, the left child of 2 in the generic tree is 5. Therefore in the binary tree, the left child of 2 is 5.
  • Since 5,6,8, and 7 are siblings, each will be the right child of the previous. Therefore, 6 becomes the right child of 5, 8 becomes the right child of 6, and 7 becomes the right child of 8. 
  • Now, the left child of 3 in the generic tree is 9. Therefore in the binary tree, the left child of 3 is 9.
  • Now, since the left child of 4 in the generic tree is 10, therefore, in the binary tree also, the left child of 4 is 10.
  • Since 10,11, and 12 are siblings, each will be the right child of the previous. Therefore,11 becomes the right child of 10, and 12 becomes the right child of 11.
  • Since the left child of 11 in the generic tree is 13, therefore, in the binary tree also, the left child of 11 is 13.
  • Hence, each node is converted here, forming the binary tree.

Frequently asked questions

  1. What is a generic tree?
    generic tree or an n-ary tree is a type of tree data structure in which each node can have at most n children, and n can be any integer value.
     
  2. 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. 
     
  3. What is a binary tree?
    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.

Key Takeaways

This article explained how to convert a generic tree into a binary tree. A prerequisite of this article was the knowledge of generic trees. To gain more knowledge about this topic, you can practice more problems. 

Some of these are: encode n-ary tree to binary treeserialize and deserialize an n-ary tree, and n-ary tree level order traversal

These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and overview student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think