Given a n-ary tree, count number of nodes which have more number of children than parents
Given a N-ary tree represented as adjacency list, we need to write a program to count all such nodes in this tree which has more number of children than its parent.
For Example,
In the above tree, the count will be 1 as there is only one such node which is ‘2’ which has more number of children than its parent. 2 has three children (4, 5 and 6) whereas its parent, 1 has only two children (2 and 3).
We can solve this problem using both BFS and DFS algorithms. We will explain here in details about how to solve this problem using BFS algorithm.
As the tree is represented using adjacency list representation. So, for any node say ‘u’ the number of children of this node can be given as adj[u].size().
Now the idea is to apply BFS on the given tree and while traversing the children of a node ‘u’ say ‘v’ we will simply check if adj[v].size() > adj[u].size().
Below is the implementation of above idea:
CPP
// C++ program to count number of nodes // which has more children than its parent #include<bits/stdc++.h> using namespace std; // function to count number of nodes // which has more children than its parent int countNodes(vector< int > adj[], int root) { int count = 0; // queue for applying BFS queue< int > q; // BFS algorithm q.push(root); while (!q.empty()) { int node = q.front(); q.pop(); // traverse children of node for ( int i=0;i<adj[node].size();i++) { // children of node int children = adj[node][i]; // if number of childs of children // is greater than number of childs // of node, then increment count if (adj[children].size() > adj[node].size()) count++; q.push(children); } } return count; } // Driver program to test above functions int main() { // adjacency list for n-ary tree vector< int > adj[10]; // construct n ary tree as shown // in above diagram adj[1].push_back(2); adj[1].push_back(3); adj[2].push_back(4); adj[2].push_back(5); adj[2].push_back(6); adj[3].push_back(9); adj[5].push_back(7); adj[5].push_back(8); int root = 1; cout << countNodes(adj, root); return 0; } |
Java
// Java program to count number of nodes // which has more children than its parent import java.util.*; class GFG { // function to count number of nodes // which has more children than its parent static int countNodes(Vector<Integer> adj[], int root) { int count = 0 ; // queue for applying BFS Queue<Integer> q = new LinkedList<>(); // BFS algorithm q.add(root); while (!q.isEmpty()) { int node = q.peek(); q.remove(); // traverse children of node for ( int i= 0 ;i<adj[node].size();i++) { // children of node int children = adj[node].get(i); // if number of childs of children // is greater than number of childs // of node, then increment count if (adj[children].size() > adj[node].size()) count++; q.add(children); } } return count; } // Driver code public static void main(String[] args) { // adjacency list for N-ary tree Vector<Integer> []adj = new Vector[ 10 ]; for ( int i= 0 ; i < 10 ; i++) { adj[i] = new Vector<>(); } // conn array tree as shown // in above diagram adj[ 1 ].add( 2 ); adj[ 1 ].add( 3 ); adj[ 2 ].add( 4 ); adj[ 2 ].add( 5 ); adj[ 2 ].add( 6 ); adj[ 3 ].add( 9 ); adj[ 5 ].add( 7 ); adj[ 5 ].add( 8 ); int root = 1 ; System.out.print(countNodes(adj, root)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to count number of nodes # which has more children than its parent from collections import deque adj = [[] for i in range ( 100 )] # function to count number of nodes # which has more children than its parent def countNodes(root): count = 0 # queue for applying BFS q = deque() # BFS algorithm q.append(root) while len (q) > 0 : node = q.popleft() # traverse children of node for i in adj[node]: # children of node children = i # if number of childs of children # is greater than number of childs # of node, then increment count if ( len (adj[children]) > len (adj[node])): count + = 1 q.append(children) return count # Driver program to test above functions # construct n ary tree as shown # in above diagram adj[ 1 ].append( 2 ) adj[ 1 ].append( 3 ) adj[ 2 ].append( 4 ) adj[ 2 ].append( 5 ) adj[ 2 ].append( 6 ) adj[ 3 ].append( 9 ) adj[ 5 ].append( 7 ) adj[ 5 ].append( 8 ) root = 1 print (countNodes(root)) # This code is contributed by mohit kumar 29 |
C#
// C# program to count number of nodes // which has more children than its parent using System; using System.Collections.Generic; class GFG { // function to count number of nodes // which has more children than its parent static int countNodes(List< int > []adj, int root) { int count = 0; // queue for applying BFS List< int > q = new List< int >(); // BFS algorithm q.Add(root); while (q.Count != 0) { int node = q[0]; q.RemoveAt(0); // traverse children of node for ( int i = 0; i < adj[node].Count; i++) { // children of node int children = adj[node][i]; // if number of childs of children // is greater than number of childs // of node, then increment count if (adj[children].Count > adj[node].Count) count++; q.Add(children); } } return count; } // Driver code public static void Main(String[] args) { // adjacency list for n-array tree List< int > []adj = new List< int >[10]; for ( int i= 0; i < 10 ; i++) { adj[i] = new List< int >(); } // conn array tree as shown // in above diagram adj[1].Add(2); adj[1].Add(3); adj[2].Add(4); adj[2].Add(5); adj[2].Add(6); adj[3].Add(9); adj[5].Add(7); adj[5].Add(8); int root = 1; Console.Write(countNodes(adj, root)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to count number of nodes // which has more children than its parent // function to count number of nodes // which has more children than its parent function countNodes(adj,root) { let count = 0; // queue for applying BFS let q = []; // BFS algorithm q.push(root); while (q.length!=0) { let node = q[0]; q.shift(); // traverse children of node for ( let i=0;i<adj[node].length;i++) { // children of node let children = adj[node][i]; // if number of childs of children // is greater than number of childs // of node, then increment count if (adj[children].length > adj[node].length) count++; q.push(children); } } return count; } // Driver code // adjacency list for n-array tree let adj = []; for (let i= 0; i < 10 ; i++) { adj[i] = []; } // conn array tree as shown // in above diagram adj[1].push(2); adj[1].push(3); adj[2].push(4); adj[2].push(5); adj[2].push(6); adj[3].push(9); adj[5].push(7); adj[5].push(8); let root = 1; document.write(countNodes(adj, root)); // This code is contributed by patel2127 </script> |
1
Time Complexity: O(n), where n is the number of nodes in the tree.
Auxiliary Space: O(n)