Check if the given n-ary tree is a binary tree

Last Updated : 29 Oct, 2024

Given an n-ary tree consisting of n nodes, the task is to check whether the given tree is binary or not.
Note: An n-ary tree is a tree where each node can have zero or more children nodes. Unlike a binary tree, which has at most two children per node (left and right), the n-ary tree allows for multiple branches or children for each node.

Examples:

Input:

Output: True
Input:
Output: False

Approach:

The idea is to use the fact that every node in a binary tree can have at most 2 children. So, for every node of the given tree, count the number of children and if for any node the count exceeds 2 then return false.

Below is the implementation of the above approach:

C++

// C++ implementation to check if the given N-ary tree is 
// a binary tree
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    vector<Node*> children;

    Node(int val) {
        data = val;
    }
};

// Function to check if the N-ary tree is
// a binary tree
void isBinaryTree(Node* root) {
    
    // Check if the tree is empty
    if (!root) {
      
        // An empty tree is considered 
      	// a binary tree
        cout << "True" << endl;  
        return;
    }

    queue<Node*> q;
    
    q.push(root);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();

        // If the current node has more than 2 children, 
        // it's not a binary tree
        if (curr->children.size() > 2) {
            cout << "False" << endl;
            return;
        }

        // Add all children of the current 
        // node to the queue
        for (auto child : curr->children) {
            q.push(child);
        }
    }

    // If no node has more than 2 children,
    // it's a binary tree
    cout << "True" << endl;
}

int main() {
    
    // Representation of given N-ary tree
    //        1
    //      /   \
    //     2      3
    //    / \   / | \
    //   4   5 6  7  8
    Node* root = new Node(1);
    root->children.push_back(new Node(2));
    root->children.push_back(new Node(3));
    root->children[0]->children.push_back(new Node(4));
    root->children[0]->children.push_back(new Node(5));
    root->children[1]->children.push_back(new Node(6));
    root->children[1]->children.push_back(new Node(7));
    root->children[1]->children.push_back(new Node(8));

    isBinaryTree(root);

    return 0;
}

Java

// Java implementation to check if the given N-ary tree is 
// a binary tree
import java.util.*;

class Node {
    int data;
    List<Node> children;

    Node(int val) {
        data = val;
        children = new ArrayList<>();
    }
}

// Function to check if the N-ary tree
// is a binary tree
class GfG {

    static void isBinaryTree(Node root) {
        
        // Check if the tree is empty
        if (root == null) {

            // An empty tree is considered 
          	// a binary tree
            System.out.println("True");
            return;
        }

        Queue<Node> q = new LinkedList<>();
        
        q.add(root);

        while (!q.isEmpty()) {
            Node curr = q.poll();

            // If the current node has more than 2 children,
            // it's not a binary tree
            if (curr.children.size() > 2) {
                System.out.println("False");
                return;
            }

            // Add all children of the current 
            // node to the queue
            for (Node child : curr.children) {
                q.add(child);
            }
        }

        // If no node has more than 2 children,
        // it's a binary tree
        System.out.println("True");
    }

    public static void main(String[] args) {
        
        // Representation of given N-ary tree
        //        1
        //      /   \
        //     2      3
        //    / \   / | \
        //   4   5 6  7  8
        Node root = new Node(1);
        root.children.add(new Node(2));
        root.children.add(new Node(3));
        root.children.get(0).children.add(new Node(4));
        root.children.get(0).children.add(new Node(5));
        root.children.get(1).children.add(new Node(6));
        root.children.get(1).children.add(new Node(7));
        root.children.get(1).children.add(new Node(8));

        isBinaryTree(root);
    }
}

Python

# Python implementation to check if the given N-ary tree is 
# a binary tree
from collections import deque

class Node:
    def __init__(self, val):
        self.data = val
        self.children = []

# Function to check if the N-ary 
# tree is a binary tree
def is_binary_tree(root):
    
    # Check if the tree is empty
    if not root:

        # An empty tree is considered
        # a binary tree
        print("True")
        return

    q = deque([root])

    while q:
        curr = q.popleft()

        # If the current node has more than 2 children,
        # it's not a binary tree
        if len(curr.children) > 2:
            print("False")
            return

        # Add all children of the current 
        # node to the queue
        for child in curr.children:
            q.append(child)

    # If no node has more than 2 children,
    # it's a binary tree
    print("True")
    
if __name__ == "__main__":

  # Representation of given N-ary tree
  #        1
  #      /   \
  #     2      3
  #    / \   / | \
  #   4   5 6  7  8
  root = Node(1)
  root.children.append(Node(2))
  root.children.append(Node(3))
  root.children[0].children.append(Node(4))
  root.children[0].children.append(Node(5))
  root.children[1].children.append(Node(6))
  root.children[1].children.append(Node(7))
  root.children[1].children.append(Node(8))

  is_binary_tree(root)

// C# implementation to check if the given N-ary tree is 
// a binary tree
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public List<Node> children;

    public Node(int val) {
        data = val;
        children = new List<Node>();
    }
}

// Function to check if the N-ary tree is
// a binary tree
class GfG {
    static void IsBinaryTree(Node root) {
        
        // Check if the tree is empty
        if (root == null) {

            // An empty tree is considered 
          	// a binary tree
            Console.WriteLine("True");
            return;
        }

        Queue<Node> q = new Queue<Node>();
        
        q.Enqueue(root);

        while (q.Count > 0) {
            Node curr = q.Dequeue();

            // If the current node has more than 2 children,
            // it's not a binary tree
            if (curr.children.Count > 2) {
                Console.WriteLine("False");
                return;
            }

            // Add all children of the current 
            // node to the queue
            foreach (Node child in curr.children) {
                q.Enqueue(child);
            }
        }

        // If no node has more than 2 children,
        // it's a binary tree
        Console.WriteLine("True");
    }

    static void Main(string[] args) {
        
        // Representation of given N-ary tree
        //        1
        //      /   \
        //     2      3
        //    / \   / | \
        //   4   5 6  7  8
        Node root = new Node(1);
        root.children.Add(new Node(2));
        root.children.Add(new Node(3));
        root.children[0].children.Add(new Node(4));
        root.children[0].children.Add(new Node(5));
        root.children[1].children.Add(new Node(6));
        root.children[1].children.Add(new Node(7));
        root.children[1].children.Add(new Node(8));

        IsBinaryTree(root);
    }
}

JavaScript

// Javascript implementation to check if the given N-ary tree is 
// a binary tree
class Node {
    constructor(val) {
        this.data = val;
        this.children = [];
    }
}

// Function to check if the N-ary tree
// is a binary tree
function isBinaryTree(root) {
    
    // Check if the tree is empty
    if (!root) {

        // An empty tree is considered
        // a binary tree
        console.log("True");
        return;
    }

    let q = [];
    
    q.push(root);

    while (q.length > 0) {
        let curr = q.shift();

        // If the current node has more
        // than 2 children, it's not a binary tree
        if (curr.children.length > 2) {
            console.log("False");
            return;
        }

        // Add all children of the current 
        // node to the queue
        for (let child of curr.children) {
            q.push(child);
        }
    }

    // If no node has more than 2 children,
    // it's a binary tree
    console.log("True");
}

// Representation of given N-ary tree
//        1
//      /   \
//     2      3
//    / \   / | \
//   4   5 6  7  8
let root = new Node(1);
root.children.push(new Node(2));
root.children.push(new Node(3));
root.children[0].children.push(new Node(4));
root.children[0].children.push(new Node(5));
root.children[1].children.push(new Node(6));
root.children[1].children.push(new Node(7));
root.children[1].children.push(new Node(8));

isBinaryTree(root);

Output

False

Time Complexity: O(n), where n is the total number of nodes, as each node is visited once during the level-order traversal.
Auxiliary Space: O(n), due to the queue storing up to n nodes in the worst case during the traversal.