Level with maximum number of nodes using DFS in a N-ary tree
Given a N-ary tree, the task is to print the level with the maximum number of nodes.
Examples:
Input : For example, consider the following tree 1 - Level 1 / \ 2 3 - Level 2 / \ \ 4 5 6 - Level 3 / \ / 7 8 9 - Level 4 Output : Level-3 and Level-4
Approach:
- Insert all the connecting nodes to a 2-D vector tree.
- Run a DFS on the tree such that height[node] = 1 + height[parent]
- Once DFS traversal is completed, increase the count[] array by 1, for every node’s level.
- Iterate from the first level to the last level, and find the level with the maximum number of nodes.
- Re-traverse from the first to the last level, and print all the levels which have the same number of maximum nodes.
Below is the implementation of the above approach.
C++
// C++ program to print the level // with maximum number of nodes #include <bits/stdc++.h> using namespace std; // Function for DFS in a tree void dfs( int node, int parent, int height[], int vis[], vector< int > tree[]) { // calculate the level of every node height[node] = 1 + height[parent]; // mark every node as visited vis[node] = 1; // iterate in the subtree for ( auto it : tree[node]) { // if the node is not visited if (!vis[it]) { // call the dfs function dfs(it, node, height, vis, tree); } } } // Function to insert edges void insertEdges( int x, int y, vector< int > tree[]) { tree[x].push_back(y); tree[y].push_back(x); } // Function to print all levels void printLevelswithMaximumNodes( int N, int vis[], int height[]) { int mark[N + 1]; memset (mark, 0, sizeof mark); int maxLevel = 0; for ( int i = 1; i <= N; i++) { // count number of nodes // in every level if (vis[i]) mark[height[i]]++; // find the maximum height of tree maxLevel = max(height[i], maxLevel); } int maxi = 0; for ( int i = 1; i <= maxLevel; i++) { maxi = max(mark[i], maxi); } // print even number of nodes cout << "The levels with maximum number of nodes are: " ; for ( int i = 1; i <= maxLevel; i++) { if (mark[i] == maxi) cout << i << " " ; } } // Driver Code int main() { // Construct the tree /* 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 */ const int N = 9; vector< int > tree[N + 1]; insertEdges(1, 2, tree); insertEdges(1, 3, tree); insertEdges(2, 4, tree); insertEdges(2, 5, tree); insertEdges(5, 7, tree); insertEdges(5, 8, tree); insertEdges(3, 6, tree); insertEdges(6, 9, tree); int height[N + 1]; int vis[N + 1] = { 0 }; height[0] = 0; // call the dfs function dfs(1, 0, height, vis, tree); // Function to print printLevelswithMaximumNodes(N, vis, height); return 0; } |
Java
// Java program to print the level // with maximum number of nodes import java.util.*; class GFG { static int N = 9 ; // Function for DFS in a tree static void dfs( int node, int parent, int height[], int vis[], Vector<Integer> tree[]) { // calculate the level of every node height[node] = 1 + height[parent]; // mark every node as visited vis[node] = 1 ; // iterate in the subtree for ( int it : tree[node]) { // if the node is not visited if (vis[it] != 1 ) { // call the dfs function dfs(it, node, height, vis, tree); } } } // Function to insert edges static void insertEdges( int x, int y, Vector<Integer> tree[]) { tree[x].add(y); tree[y].add(x); } // Function to print all levels static void printLevelswithMaximumNodes( int N, int vis[], int height[]) { int []mark = new int [N + 1 ]; int maxLevel = 0 ; for ( int i = 1 ; i <= N; i++) { // count number of nodes // in every level if (vis[i] == 1 ) mark[height[i]]++; // find the maximum height of tree maxLevel = Math.max(height[i], maxLevel); } int maxi = 0 ; for ( int i = 1 ; i <= maxLevel; i++) { maxi = Math.max(mark[i], maxi); } // print even number of nodes System.out.print( "The levels with maximum number of nodes are: " ); for ( int i = 1 ; i <= maxLevel; i++) { if (mark[i] == maxi) System.out.print(i+ " " ); } } // Driver Code public static void main(String[] args) { // Construct the tree /* 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 */ Vector<Integer> []tree = new Vector[N + 1 ]; for ( int i= 0 ; i < N + 1 ; i++) tree[i] = new Vector<Integer>(); insertEdges( 1 , 2 , tree); insertEdges( 1 , 3 , tree); insertEdges( 2 , 4 , tree); insertEdges( 2 , 5 , tree); insertEdges( 5 , 7 , tree); insertEdges( 5 , 8 , tree); insertEdges( 3 , 6 , tree); insertEdges( 6 , 9 , tree); int height[] = new int [N + 1 ]; int vis[] = new int [N + 1 ]; height[ 0 ] = 0 ; // call the dfs function dfs( 1 , 0 , height, vis, tree); // Function to print printLevelswithMaximumNodes(N, vis, height); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to print the level # with the maximum number of nodes # Function for DFS in a tree def dfs(node, parent, height, vis, tree): # calculate the level of every node height[node] = 1 + height[parent] # mark every node as visited vis[node] = 1 # iterate in the subtree for it in tree[node]: # if the node is not visited if vis[it] = = 0 : # call the dfs function dfs(it, node, height, vis, tree) # Function to insert edges def insertEdges(x, y, tree): tree[x].append(y) tree[y].append(x) # Function to print all levels def printLevelswithMaximumNodes(N, vis, height): mark = [ 0 ] * (N + 1 ) maxLevel = 0 for i in range ( 1 , N + 1 ): # count number of nodes # in every level if vis[i] = = 1 : mark[height[i]] + = 1 # find the maximum height of tree maxLevel = max (height[i], maxLevel) maxi = 0 for i in range ( 1 , maxLevel + 1 ): maxi = max (mark[i], maxi) # print even number of nodes print ( "The levels with maximum number" , "of nodes are:" , end = " " ) for i in range ( 1 , maxLevel + 1 ): if mark[i] = = maxi: print (i, end = " " ) # Driver Code if __name__ = = "__main__" : # Construct the tree N = 9 # Create an empty 2-D list tree = [[] for i in range (N + 1 )] insertEdges( 1 , 2 , tree) insertEdges( 1 , 3 , tree) insertEdges( 2 , 4 , tree) insertEdges( 2 , 5 , tree) insertEdges( 5 , 7 , tree) insertEdges( 5 , 8 , tree) insertEdges( 3 , 6 , tree) insertEdges( 6 , 9 , tree) height = [ None ] * (N + 1 ) vis = [ 0 ] * (N + 1 ) height[ 0 ] = 0 # call the dfs function dfs( 1 , 0 , height, vis, tree) # Function to print printLevelswithMaximumNodes(N, vis, height) # This code is contributed # by Rituraj Jain |
C#
// C# program to print the level // with maximum number of nodes using System; using System.Collections.Generic; public class GFG { static int N = 9; // Function for DFS in a tree static void dfs( int node, int parent, int []height, int []vis, List< int > []tree) { // calculate the level of every node height[node] = 1 + height[parent]; // mark every node as visited vis[node] = 1; // iterate in the subtree foreach ( int it in tree[node]) { // if the node is not visited if (vis[it] != 1) { // call the dfs function dfs(it, node, height, vis, tree); } } } // Function to insert edges static void insertEdges( int x, int y, List< int > []tree) { tree[x].Add(y); tree[y].Add(x); } // Function to print all levels static void printLevelswithMaximumNodes( int N, int []vis, int []height) { int []mark = new int [N + 1]; int maxLevel = 0; for ( int i = 1; i <= N; i++) { // count number of nodes // in every level if (vis[i] == 1) mark[height[i]]++; // find the maximum height of tree maxLevel = Math.Max(height[i], maxLevel); } int maxi = 0; for ( int i = 1; i <= maxLevel; i++) { maxi = Math.Max(mark[i], maxi); } // print even number of nodes Console.Write( "The levels with maximum number of nodes are: " ); for ( int i = 1; i <= maxLevel; i++) { if (mark[i] == maxi) Console.Write(i+ " " ); } } // Driver Code public static void Main(String[] args) { // Construct the tree /* 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 */ List< int > []tree = new List< int >[N + 1]; for ( int i= 0; i < N + 1; i++) tree[i] = new List< int >(); insertEdges(1, 2, tree); insertEdges(1, 3, tree); insertEdges(2, 4, tree); insertEdges(2, 5, tree); insertEdges(5, 7, tree); insertEdges(5, 8, tree); insertEdges(3, 6, tree); insertEdges(6, 9, tree); int []height = new int [N + 1]; int []vis = new int [N + 1]; height[0] = 0; // call the dfs function dfs(1, 0, height, vis, tree); // Function to print printLevelswithMaximumNodes(N, vis, height); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to print the level // with maximum number of nodes let N = 9; let tree = new Array(N + 1); let height = new Array(N + 1); height.fill(0); let vis = new Array(N + 1); vis.fill(0); // Function for DFS in a tree function dfs(node, parent, tree) { // calculate the level of every node height[node] = 1 + height[parent]; // mark every node as visited vis[node] = 1; // iterate in the subtree for (let it = 0; it < tree[node].length; it++) { // if the node is not visited if (vis[tree[node][it]] != 1) { // call the dfs function dfs(tree[node][it], node, tree); } } } // Function to insert edges function insertEdges(x, y, tree) { tree[x].push(y); tree[y].push(x); } // Function to print all levels function printLevelswithMaximumNodes(N) { let mark = new Array(N + 1); mark.fill(0); let maxLevel = 0; for (let i = 1; i <= N; i++) { // count number of nodes // in every level if (vis[i] == 1) mark[height[i]]++; // find the maximum height of tree maxLevel = Math.max(height[i], maxLevel); } let maxi = 0; for (let i = 1; i <= maxLevel; i++) { maxi = Math.max(mark[i], maxi); } // print even number of nodes document.write( "The levels with maximum number of nodes are: " ); for (let i = 1; i <= maxLevel; i++) { if (mark[i] == maxi) document.write(i+ " " ); } } // Construct the tree /* 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 */ for (let i= 0; i < N + 1; i++) { tree[i] = []; } insertEdges(1, 2, tree); insertEdges(1, 3, tree); insertEdges(2, 4, tree); insertEdges(2, 5, tree); insertEdges(5, 7, tree); insertEdges(5, 8, tree); insertEdges(3, 6, tree); insertEdges(6, 9, tree); height[0] = 0; // call the dfs function dfs(1, 0, tree); // Function to print printLevelswithMaximumNodes(N); </script> |
Output
The levels with maximum number of nodes are: 3 4
Complexity Analysis:
- Time Complexity: O(N), as we are using recursion for traversing all the nodes, though we are using a for loop to traverse all the N nodes, but we are calling the function only if the node is node visited therefore the effective time complexity will be O(N).
- Auxiliary Space: O(N), as we are using extra space for an array to keep track of the visited nodes.