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

## 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?

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, 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?

A **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

**What is a generic tree?**

A**generic tree**or an**n-ary tree**is a type of treein which each node can have at most n children, and n can be any integer value.__data structure__

**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 ahaving a root node and at most two children nodes. Each of these children forms the left subtree and the right subtree.__Data Structure__

## 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 tree__, __serialize 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!

Comments

## No comments yet

## Be the first to share what you think