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.

Implementation

• C
• C++
• Java
• Python
• JS
• C#

C

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    struct TreeNode** child;
    int childCount;
} TreeNode;

TreeNode* createNode(int data, int childCount) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->childCount = childCount;
    node->child = (TreeNode**)malloc(childCount * sizeof(TreeNode*));
    return node;
}

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

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

    for (int i = 2; i < root->childCount; 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;
    }
    printf("%d ", root->data);
    printTree(root->left);
    printTree(root->right);
}

int main() {
    TreeNode* root = createNode(5, 3);
    root->child[0] = createNode(8, 2);
    root->child[1] = createNode(2, 0);
    root->child[2] = createNode(1, 0);

    root->child[0]->child[0] = createNode(3, 0);
    root->child[0]->child[1] = createNode(4, 0);

    TreeNode* binaryTree = genericToBinary(root);
    printTree(binaryTree);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#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

Java

import java.util.*;

class TreeNode {
    int data;
    TreeNode left, right;
    List<TreeNode> children;

    TreeNode(int data) {
        this.data = data;
        this.left = this.right = null;
        this.children = new ArrayList<>();
    }
}

public class GenericToBinaryTree {
    public static TreeNode genericToBinary(TreeNode root) {
        if (root == null || root.children.isEmpty()) {
            return root;
        }

        root.left = genericToBinary(root.children.get(0));
        if (root.children.size() > 1) {
            root.right = genericToBinary(root.children.get(1));
        }

        TreeNode rightNode = root.right;
        for (int i = 2; i < root.children.size(); i++) {
            while (rightNode != null && rightNode.left != null) {
                rightNode = rightNode.left;
            }
            rightNode.left = genericToBinary(root.children.get(i));
        }

        return root;
    }

    public static void printTree(TreeNode root) {
        if (root == null) return;
        System.out.print(root.data + " ");
        printTree(root.left);
        printTree(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.children.add(new TreeNode(8));
        root.children.add(new TreeNode(2));
        root.children.add(new TreeNode(1));

        root.children.get(0).children.add(new TreeNode(3));
        root.children.get(0).children.add(new TreeNode(4));

        TreeNode binaryTree = genericToBinary(root);
        printTree(binaryTree);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.children = []

def generic_to_binary(root):
    if not root or not root.children:
        return root

    root.left = generic_to_binary(root.children[0])
    
    if len(root.children) > 1:
        root.right = generic_to_binary(root.children[1])

    right_node = root.right
    for i in range(2, len(root.children)):
        while right_node and right_node.left:
            right_node = right_node.left
        right_node.left = generic_to_binary(root.children[i])

    return root

def print_tree(root):
    if not root:
        return
    print(root.data, end=" ")
    print_tree(root.left)
    print_tree(root.right)

root = TreeNode(5)
root.children.append(TreeNode(8))
root.children.append(TreeNode(2))
root.children.append(TreeNode(1))

root.children[0].children.append(TreeNode(3))
root.children[0].children.append(TreeNode(4))

binary_tree = generic_to_binary(root)
print_tree(binary_tree)

You can also try this code with Online Python Compiler

Run Code

JS

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.children = [];
    }
}

function genericToBinary(root) {
    if (!root || root.children.length === 0) {
        return root;
    }

    root.left = genericToBinary(root.children[0]);

    if (root.children.length > 1) {
        root.right = genericToBinary(root.children[1]);
    }

    let rightNode = root.right;
    for (let i = 2; i < root.children.length; i++) {
        while (rightNode && rightNode.left) {
            rightNode = rightNode.left;
        }
        rightNode.left = genericToBinary(root.children[i]);
    }

    return root;
}

function printTree(root) {
    if (!root) return;
    process.stdout.write(root.data + " ");
    printTree(root.left);
    printTree(root.right);
}

const root = new TreeNode(5);
root.children.push(new TreeNode(8));
root.children.push(new TreeNode(2));
root.children.push(new TreeNode(1));

root.children[0].children.push(new TreeNode(3));
root.children[0].children.push(new TreeNode(4));

const binaryTree = genericToBinary(root);
printTree(binaryTree);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class TreeNode {
    public int Data;
    public TreeNode Left, Right;
    public List<TreeNode> Children;

    public TreeNode(int data) {
        Data = data;
        Left = Right = null;
        Children = new List<TreeNode>();
    }
}

class GenericToBinaryTree {
    public static TreeNode GenericToBinary(TreeNode root) {
        if (root == null || root.Children.Count == 0) {
            return root;
        }

        root.Left = GenericToBinary(root.Children[0]);

        if (root.Children.Count > 1) {
            root.Right = GenericToBinary(root.Children[1]);
        }

        TreeNode rightNode = root.Right;
        for (int i = 2; i < root.Children.Count; i++) {
            while (rightNode != null && rightNode.Left != null) {
                rightNode = rightNode.Left;
            }
            rightNode.Left = GenericToBinary(root.Children[i]);
        }

        return root;
    }

    public static void PrintTree(TreeNode root) {
        if (root == null) return;
        Console.Write(root.Data + " ");
        PrintTree(root.Left);
        PrintTree(root.Right);
    }

    public static void Main() {
        TreeNode root = new TreeNode(5);
        root.Children.Add(new TreeNode(8));
        root.Children.Add(new TreeNode(2));
        root.Children.Add(new TreeNode(1));

        root.Children[0].Children.Add(new TreeNode(3));
        root.Children[0].Children.Add(new TreeNode(4));

        TreeNode binaryTree = GenericToBinary(root);
        PrintTree(binaryTree);
    }
}

Output:

583421

Time Complexity

The time complexity of this approach is O(N), where N is the number of nodes in the given generic tree.

• Each node is visited once and processed to form the binary tree.
• Since every node is converted exactly once and each recursive call operates on a different child node, the total operations remain proportional to N.
• Thus, the overall time complexity is O(N).

Space Complexity

The space complexity of this approach is O(N) due to recursive function calls.

• The recursion depth depends on the structure of the tree. In the worst case (a skewed tree), the recursive calls will go up to N levels deep.
• This results in an O(N) space usage in the function call stack.
• No extra data structures are used apart from the recursive stack, ensuring the total space complexity remains O(N).

Frequently Asked Questions

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. 

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