Number of ways to traverse an N-ary tree - GeeksforGeeks

Number of ways to traverse an N-ary tree - GeeksforGeeks
Given an n-ary tree, count number of ways to traverse an n-ary (or a Directed Acyclic Graph) tree starting from the root vertex.

int calculateWays(Node * root)

{

   int ways = 1;  // Initialize result

 

   // If the tree is empty there is no way of traversing

   // the tree.

   if (root == NULL)

      return 0;

 

   // Create a queue and enqueue root to it.

   queue<Node *>q;

   q.push(root);

 

   // Level order traversal.

   while (!q.empty())

   {

      int n = q.size();

      while (n>0)

      {

         // Dequeue an item from queue and print it

         Node * p = q.front();

         q.pop();

 

         // The number of ways is the product of

         // factorials of number of children of each node.

         ways = ways*(factorial(p->child.size()));

 

         // Enqueue all childrent of the dequeued item

         for (int i=0; i<p->child.size(); i++)

            q.push(p->child[i]);

         n--;

      }

    }

 

   return(ways);

}

Read full article from Number of ways to traverse an N-ary tree - GeeksforGeeks