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 treevoid 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 edgesvoid insertEdges(int x, int y, vector<int> tree[]){ tree[x].push_back(y); tree[y].push_back(x);}// Function to print all levelsvoid 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 Codeint 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 Codeif __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.
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!
