Count of subtrees possible from an N-ary Tree

0 0 7 minutes read

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)) % (10⁹ + 7).
- Update the value of count as (count + res) % (10⁹ + 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 300004
using namespace std;
 
// Adjacency list to
// represent the graph
vector<int> graph[MAX];
int mod = 1e9 + 7;
 
// Stores the count of subtrees
// possible from given N-ary Tree
int ans = 0;
 
// Utility function to count the number of
// subtrees possible from given N-ary Tree
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].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 tree
void 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 Code
int main()
{
    int N = 3;
 
    vector<pair<int, int> > adj
        = { { 0, 1 }, { 1, 2 } };
 
    countSubtrees(N, adj);
 
    return 0;
}

Java

// Java program of above approach
import java.util.*;
 
class GFG{
     
static int MAX = 300004;
 
// Adjacency list to
// represent the graph
static ArrayList<ArrayList<Integer>> 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.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 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.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 code
public 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 approach
MAX = 300004
 
# Adjacency list to
# represent the graph
graph = [[] for i in range(MAX)]
mod = 10**9 + 7
 
# Stores the count of subtrees
# possible from given N-ary Tree
ans = 0
 
# Utility function to count the number of
# subtrees possible from given N-ary Tree
def 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 tree
def 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 Code
if __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 approach
using 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 approach
 
var MAX = 300004;
 
// Adjacency list to
// represent the graph
var graph = Array.from(Array(MAX),()=>new Array());
var mod = 1000000007;
 
// Stores the count of subtrees
// possible from given N-ary Tree
var ans = 0;
 
// Utility function to count the number of
// subtrees possible from given N-ary Tree
function 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 tree
function 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 Code
var N = 3;
var adj
    = [[ 0, 1 ], [1, 2 ]];
countSubtrees(N, adj);
 
// This code is contributed by itsok.
</script>

Output:

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 zambiatek!