Given an n-ary tree, the task is to check whether the given tree is binary or not.
Examples:
Input:
A
/ \
B C
/ \ \
D E F
Output: Yes
Input:
A
/ | \
B C D
\
F
Output: No
Approach: 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 print No else print Yes.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure of a node// of an n-ary treestruct Node { char key; vector<Node*> child;};// Utility function to create// a new tree nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; return temp;}// Function that returns true// if the given tree is binarybool isBinaryTree(struct Node* root){ // Base case if (!root) return true; // Count will store the number of // children of the current node int count = 0; for (int i = 0; i < root->child.size(); i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root->child[i])) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true;}// Driver codeint main(){ Node* root = newNode('A'); (root->child).push_back(newNode('B')); (root->child).push_back(newNode('C')); (root->child[0]->child).push_back(newNode('D')); (root->child[0]->child).push_back(newNode('E')); (root->child[1]->child).push_back(newNode('F')); if (isBinaryTree(root)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Structure of a node// of an n-ary treestatic class Node { int key; Vector<Node> child = new Vector<Node>();};// Utility function to create// a new tree nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; return temp;}// Function that returns true// if the given tree is binarystatic boolean isBinaryTree(Node root){ // Base case if (root == null) return true; // Count will store the number of // children of the current node int count = 0; for (int i = 0; i < root.child.size(); i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root.child.get(i))) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true;}// Driver codepublic static void main(String[] args) { Node root = newNode('A'); (root.child).add(newNode('B')); (root.child).add(newNode('C')); (root.child.get(0).child).add(newNode('D')); (root.child.get(0).child).add(newNode('E')); (root.child.get(1).child).add(newNode('F')); if (isBinaryTree(root)) System.out.println("Yes"); else System.out.println("No");}} // This code is contributed by PrinciRaj1992 |
Python3
# Python implementation of the approach# Structure of a node of an n-ary treeclass Node: def __init__(self,key): self.key = key self.child = [] # Utility function to create# a new tree nodedef newNode(key): temp = Node(key) return temp# Function that returns true# if the given tree is binarydef isBinaryTree(root): # Base case if (root == None): return True # Count will store the number of # children of the current node count = 0 for i in range(len(root.child)): # If any child of the current node doesn't # satisfy the condition of being # a binary tree node if (isBinaryTree(root.child[i]) == False): return False # Increment the count of children count += 1 # If current node has more # than 2 children if (count > 2): return False return True# Driver coderoot = newNode('A')(root.child).append(newNode('B'))(root.child).append(newNode('C'))(root.child[0].child).append(newNode('D'))(root.child[0].child).append(newNode('E'))(root.child[1].child).append(newNode('F'))if (isBinaryTree(root)): print("Yes")else: print("No")# This code is contributed by shinjanpatra |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG {// Structure of a node// of an n-ary treepublic class Node { public int key; public List<Node> child = new List<Node>();};// Utility function to create// a new tree nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; return temp;}// Function that returns true// if the given tree is binarystatic bool isBinaryTree(Node root){ // Base case if (root == null) return true; // Count will store the number of // children of the current node int count = 0; for (int i = 0; i < root.child.Count; i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root.child[i])) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true;}// Driver codepublic static void Main(String[] args) { Node root = newNode('A'); (root.child).Add(newNode('B')); (root.child).Add(newNode('C')); (root.child[0].child).Add(newNode('D')); (root.child[0].child).Add(newNode('E')); (root.child[1].child).Add(newNode('F')); if (isBinaryTree(root)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Structure of a node of an n-ary treeclass Node{ constructor(key) { this.key = key; this.child = []; }}// Utility function to create// a new tree nodefunction newNode(key){ let temp = new Node(key); return temp;}// Function that returns true// if the given tree is binaryfunction isBinaryTree(root){ // Base case if (root == null) return true; // Count will store the number of // children of the current node let count = 0; for(let i = 0; i < root.child.length; i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root.child[i])) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true;}// Driver codelet root = newNode('A');(root.child).push(newNode('B'));(root.child).push(newNode('C'));(root.child[0].child).push(newNode('D'));(root.child[0].child).push(newNode('E'));(root.child[1].child).push(newNode('F'));if (isBinaryTree(root)) document.write("Yes");else document.write("No");// This code is contributed by divyeshrabadiya07</script> |
Output:
Yes
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More Info here on that Topic: geeksforgeeks.org/check-if-the-given-n-ary-tree-is-a-binary-tree/ […]