Conversion of General Tree to Binary Tree

Binary trees are one of the fundamental as well as important data structures in computer science. And understanding their properties, operations, and traversal algorithms provides a solid foundation to solve more difficult questions.
So, In this blog, you will get to know the “Conversion of General Tree to Binary Tree”.
To convert a general tree into a binary tree, we are using a technique called “left-child, right-sibling” (LC-RS) representation.

What is LC-RS representation?

In this representation, each node in the general tree is represented as a node in the binary tree. 

So, In the binary tree, 

1. The left child of the general tree will represent the first child of the binary tree.
2. And the right sibling in the general tree will represent the next sibling in the binary tree.

Explain the conversion of general tree into the binary tree with example :

So, Converting a general tree into a binary tree involves mapping the structure and nodes of the general tree into a binary tree.
Here’s an explanation of the conversion of the general tree to a binary tree in data structure:
Let’s consider the following general tree as an example:

So, In the general tree, each node can have any number of children. However, in a binary tree, each node can have at most two children that is a left child and a right child.
So, to convert the general tree into a binary tree, we can follow these steps:

1. In this case, node A will be the root of the binary tree.
2.  For each child node of a parent in the general tree, choose one child as the left child node and convert the remaining child node in the right subtree of the left child.
3.  Starting with node A has three children: B, C, and D. We select node B as the left child node of A node and convert the remaining children (C and D) into the right subtree of B’s left node.
4. Now, we continue the conversion process with node B. It has two children: K (from the general tree) and C (from the binary tree). We choose node K as the left child of B and convert the remaining child C into the right subtree of B as explained above. 
5. Then, in the same way, we move to node C. It has three children (H, I, J). We select H as a left node and Choose I and J node as a right subtree of node H.
6. After this, we move to node D. Node D has two children E and F. We choose E as a left node for Node D and choose Node F as a right node for Node E. 
7. Finally, we come to Node F and it has only one child node (G). We will choose node G as the left node for Node F.

So, in this way, we convert our general tree to a binary tree.

Code for Conversion of general tree to binary tree in C++:

#include <iostream>

using namespace std;

// Structure for a node in the binary tree
struct BinaryTreeNode {
    char data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;

    BinaryTreeNode(char value): data(value), left(nullptr), right(nullptr) {}
};

// Structure for a node in the general tree
struct GeneralTreeNode {
    char data;
    GeneralTreeNode* firstChild;
    GeneralTreeNode* nextChild;

    GeneralTreeNode(char value)
        : data(value), firstChild(nullptr), nextChild(nullptr) {}
};

// Function to convert a general tree to a binary tree
BinaryTreeNode* convertGeneralTreeToBinaryTree(GeneralTreeNode* generalNode) {
    if (generalNode == nullptr)
        return nullptr;

    // Create a corresponding node in the binary tree
    BinaryTreeNode* binaryNode = new BinaryTreeNode(generalNode->data);

    // Recursively convert the first child and set it as the left child of the binary node
    binaryNode->left = convertGeneralTreeToBinaryTree(generalNode->firstChild);

    // Recursively convert the next sibling and set it as the right child of the binary node
    binaryNode->right = convertGeneralTreeToBinaryTree(generalNode->nextChild);

    return binaryNode;
}

// Function to print the binary tree in pre-order traversal
void preOrderTraversal(BinaryTreeNode* node) {
    if (node == nullptr)
        return;

    cout << node->data << " ";
    preOrderTraversal(node->left);
    preOrderTraversal(node->right);
}

int main() {
    // Creating a sample general tree
    GeneralTreeNode* A = new GeneralTreeNode('A');
    GeneralTreeNode* B = new GeneralTreeNode('B');
    GeneralTreeNode* C = new GeneralTreeNode('C');
    GeneralTreeNode* D = new GeneralTreeNode('D');
    GeneralTreeNode* E = new GeneralTreeNode('E');
    GeneralTreeNode* F = new GeneralTreeNode('F');
    GeneralTreeNode* G = new GeneralTreeNode('G');

    A->firstChild = B;
    B->firstChild = E;
    B->nextChild = C;
    C->nextChild = D;
    D->firstChild = G;
    E->nextChild = F;

    // Convert general tree to binary tree
    BinaryTreeNode* binaryTreeRoot = convertGeneralTreeToBinaryTree(A);

    // Print the binary tree in pre-order traversal
    cout << "Binary Tree (Pre-order traversal): ";
    preOrderTraversal(binaryTreeRoot);
    cout << endl;
}

In the above binary tree, each node has a left child pointing to its first child in the general tree and the right sibling points to its next sibling in the general tree.

Explanation:

Here’s an explanation of the above code:

1. The code will start by including the necessary header files.

2. Next, we will define the structures for the binary tree node (BinaryTreeNode) and the general tree node (GeneralTreeNode).

3. Next, we will make a convertGeneralTreeToBinaryTree function to convert a general tree to a binary tree using the LC-RS representation approach. 

4. The above function will take a pointer from GeneralTreeNode as the parameter that represents the current node in the general tree and returns a BinaryTreeNode pointer (binaryNode) representing the form of the corresponding node in the binary tree.

5. Inside the convertGeneralTreeToBinaryTree function:

• If the current node value is nullptr which indicates the end of a branch, the function will return “nullptr” to show the end of the related branch in the binary tree.
• Otherwise, a new binary tree node (BinaryTreeNode) is created with the same data as the current general tree node (GeneralTreeNode).
• The function will recursively convert the first child of the current general tree node and sets it as the left child of the created binary tree node (binaryNode).
•  After that, the function will recursively convert the next sibling (nextChild) of the current general tree node and sets it as the right child node of the created binary tree node successfully.

6. Here, the preOrderTraversal function is defined to perform pre-order traversal on the binary tree and print the nodes properly by following the pre-order rule. So, this function will take a BinaryTreeNode pointer as a parameter that represents the current node to start the traversal.

7. Next we make the main function,

• Here, general tree nodes are connected to form the binary tree structure.

• Then, we call the convertGeneralTreeToBinaryTree function and pass the root of the general tree (`A`) to obtain the root of the binary tree (`binaryTreeRoot`).

• Then call the “preOrderTraversal” function and pass the binaryTreeRoot variable.

So, finally, our general tree will be converted to the binary tree and it will print the binary tree nodes in the pre-order traversal.

Conclusion:

So, the “conversion of general tree to binary tree” program is very easy, all we have to do is for each child node of a parent in the general tree, choose one child as the left child node and convert the remaining child node into the right subtree of the left child in the new binary tree.