Given an N-ary tree consisting of N nodes having values 0 to (N – 1), the task is to find the total number of subtrees present in the given tree. Since the count can be very large, so print the count modulo 1000000007.
Examples:
Input: N = 3
0
/
1
/
2
Output: 7
Explanation:
The total number of subtrees nodes are {}, {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 1, 2}.Input: N = 2
0
/
1
Output: 4
Approach: The approach for solving the given problem is to perform DFS Traversal on the given tree. Follow the steps below to solve the problem:
- Initialize a variable, say count as 0, to store the count of the total number of subtrees present in the given tree.
- Declare a function DFS(int src, int parent) to count the number of subtrees for the node src and perform the following operations:
- Initialize a variable, say res as 1.
- Traverse the adjacency list of the current node and if the node in the adjacency list, say X is not the same as the parent node, then recursively call the DFS function for the node X and node src as the parent node as DFS(X, src).
- Let the value returned to the above recursive call is value, then update the value of res as (res * (value + 1)) % (109 + 7).
- Update the value of count as (count + res) % (109 + 7).
- Return the value of res from each recursive call.
- Call the function DFS() for the root node 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>#define MAX 300004using namespace std;// Adjacency list to// represent the graphvector<int> graph[MAX];int mod = 1e9 + 7;// Stores the count of subtrees// possible from given N-ary Treeint ans = 0;// Utility function to count the number of// subtrees possible from given N-ary Treeint countSubtreesUtil(int cur, int par){ // Stores the count of subtrees // when cur node is the root int res = 1; // Traverse the adjacency list for (int i = 0; i < graph[cur].size(); i++) { // Iterate over every ancestor int v = graph[cur][i]; if (v == par) continue; // Calculate product of the number // of subtrees for each child node res = (res * (countSubtreesUtil( v, cur) + 1)) % mod; } // Update the value of ans ans = (ans + res) % mod; // Return the resultant count return res;}// Function to count the number of// subtrees in the given treevoid countSubtrees(int N, vector<pair<int, int> >& adj){ // Initialize an adjacency matrix for (int i = 0; i < N - 1; i++) { int a = adj[i].first; int b = adj[i].second; // Add the edges graph[a].push_back(b); graph[b].push_back(a); } // Function Call to count the // number of subtrees possible countSubtreesUtil(1, 1); // Print count of subtrees cout << ans + 1;}// Driver Codeint main(){ int N = 3; vector<pair<int, int> > adj = { { 0, 1 }, { 1, 2 } }; countSubtrees(N, adj); return 0;} |
Java
// Java program of above approachimport java.util.*;class GFG{ static int MAX = 300004;// Adjacency list to// represent the graphstatic ArrayList<ArrayList<Integer>> graph;static long mod = (long)1e9 + 7; // Stores the count of subtrees// possible from given N-ary Treestatic int ans = 0; // Utility function to count the number of// subtrees possible from given N-ary Treestatic int countSubtreesUtil(int cur, int par){ // Stores the count of subtrees // when cur node is the root int res = 1; // Traverse the adjacency list for(int i = 0; i < graph.get(cur).size(); i++) { // Iterate over every ancestor int v = graph.get(cur).get(i); if (v == par) continue; // Calculate product of the number // of subtrees for each child node res = (int)((res * (countSubtreesUtil( v, cur) + 1)) % mod); } // Update the value of ans ans = (int)((ans + res) % mod); // Return the resultant count return res;} // Function to count the number of// subtrees in the given treestatic void countSubtrees(int N, int[][] adj){ // Initialize an adjacency matrix for(int i = 0; i < N - 1; i++) { int a = adj[i][0]; int b = adj[i][1]; // Add the edges graph.get(a).add(b); graph.get(b).add(a); } // Function Call to count the // number of subtrees possible countSubtreesUtil(1, 1); // Print count of subtrees System.out.println(ans + 1);}// Driver codepublic static void main(String[] args){ int N = 3; int[][] adj = { { 0, 1 }, { 1, 2 } }; graph = new ArrayList<>(); for(int i = 0; i < MAX; i++) graph.add(new ArrayList<>()); countSubtrees(N, adj);}}// This code is contributed by offbeat |
Python3
# Python3 program of the above approachMAX = 300004# Adjacency list to# represent the graphgraph = [[] for i in range(MAX)]mod = 10**9 + 7# Stores the count of subtrees# possible from given N-ary Treeans = 0# Utility function to count the number of# subtrees possible from given N-ary Treedef countSubtreesUtil(cur, par): global mod, ans # Stores the count of subtrees # when cur node is the root res = 1 # Traverse the adjacency list for i in range(len(graph[cur])): # Iterate over every ancestor v = graph[cur][i] if (v == par): continue # Calculate product of the number # of subtrees for each child node res = (res * (countSubtreesUtil(v, cur)+ 1)) % mod # Update the value of ans ans = (ans + res) % mod # Return the resultant count return res# Function to count the number of# subtrees in the given treedef countSubtrees(N, adj): # Initialize an adjacency matrix for i in range(N-1): a = adj[i][0] b = adj[i][1] # Add the edges graph[a].append(b) graph[b].append(a) # Function Call to count the # number of subtrees possible countSubtreesUtil(1, 1) # Print count of subtrees print (ans + 1)# Driver Codeif __name__ == '__main__': N = 3 adj = [ [ 0, 1 ], [ 1, 2 ] ] countSubtrees(N, adj)# This code is contributed by mohit kumar 29. |
C#
// C# program of above approachusing System;using System.Collections.Generic;public class GFG { static int MAX = 300004; // Adjacency list to // represent the graph static List<List<int>> graph; static long mod = (long) 1e9 + 7; // Stores the count of subtrees // possible from given N-ary Tree static int ans = 0; // Utility function to count the number of // subtrees possible from given N-ary Tree static int countSubtreesUtil(int cur, int par) { // Stores the count of subtrees // when cur node is the root int res = 1; // Traverse the adjacency list for (int i = 0; i < graph[cur].Count; i++) { // Iterate over every ancestor int v = graph[cur][i]; if (v == par) continue; // Calculate product of the number // of subtrees for each child node res = (int) ((res * (countSubtreesUtil(v, cur) + 1)) % mod); } // Update the value of ans ans = (int) ((ans + res) % mod); // Return the resultant count return res; } // Function to count the number of // subtrees in the given tree static void countSubtrees(int N, int[,] adj) { // Initialize an adjacency matrix for (int i = 0; i < N - 1; i++) { int a = adj[i,0]; int b = adj[i,1]; // Add the edges graph[a].Add(b); graph[b].Add(a); } // Function Call to count the // number of subtrees possible countSubtreesUtil(1, 1); // Print count of subtrees Console.WriteLine(ans + 1); } // Driver code public static void Main(String[] args) { int N = 3; int[,] adj = { { 0, 1 }, { 1, 2 } }; graph = new List<List<int>>(); for (int i = 0; i < MAX; i++) graph.Add(new List<int>()); countSubtrees(N, adj); }}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program of the above approachvar MAX = 300004;// Adjacency list to// represent the graphvar graph = Array.from(Array(MAX),()=>new Array());var mod = 1000000007;// Stores the count of subtrees// possible from given N-ary Treevar ans = 0;// Utility function to count the number of// subtrees possible from given N-ary Treefunction countSubtreesUtil(cur, par){ // Stores the count of subtrees // when cur node is the root var res = 1; // Traverse the adjacency list for (var i = 0; i < graph[cur].length; i++) { // Iterate over every ancestor var v = graph[cur][i]; if (v == par) continue; // Calculate product of the number // of subtrees for each child node res = (res * (countSubtreesUtil( v, cur) + 1)) % mod; } // Update the value of ans ans = (ans + res) % mod; // Return the resultant count return res;}// Function to count the number of// subtrees in the given treefunction countSubtrees(N, adj){ // Initialize an adjacency matrix for (var i = 0; i < N - 1; i++) { var a = adj[i][0]; var b = adj[i][1]; // Add the edges graph[a].push(b); graph[b].push(a); } // Function Call to count the // number of subtrees possible countSubtreesUtil(1, 1); // Print count of subtrees document.write( ans + 1);}// Driver Codevar N = 3;var adj = [[ 0, 1 ], [1, 2 ]];countSubtrees(N, adj);// This code is contributed by itsok.</script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
